usaco-3.1-PROB Shaping Regions-漂浮法

2020-11-18 06:19

阅读：642

标签：style blog color os io 2014

漂浮法，顾名思义，就是一块块的往上飘。

以逆序来进行放置，即n to 1。逆序的好处在于放置一个矩形后，俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了，所以可直接统计，为递归创造了条件。每放一个矩形，可以想象成将其扔入一密度很大的海水底部，海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形，继续上浮，直到浮出水面。于是想到用个递归来模拟上浮过程。

/*
ID: rowanha3
LANG: C++
TASK: rect1
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n;
struct list
{
    int x1,y1;
    int x2,y2;
    int cl;
    friend bool operator =x2||y1>=y2)return;
    if(y>n)
    {
        ans[color]+=(x2-x1)*(y2-y1);
        return;
    }
    struct list p;
    p=rec[y];
    if(y1p.y2)dos(min(x1,p.x2),max(y1,p.y2),min(p.x2,x2),y2,color,y+1);
    if(x1p.x2)dos(max(p.x2,x1),max(p.y1,y1),x2,max(p.y1,y2),color,y+1);
}
int main(){
    freopen("rect1.in","r",stdin);
    freopen("rect1.out","w",stdout);
    int a,b,i;
    scanf("%d%d%d",&a,&b,&n);
    for(i=1;i=0;i--)
    {
        dos(rec[i].x1,rec[i].y1,rec[i].x2,rec[i].y2,rec[i].cl,i+1);
    }
    for(i=1;i
usaco-3.1-PROB Shaping Regions-漂浮法,搜素材,soscw.com
usaco-3.1-PROB Shaping Regions-漂浮法
标签：style   blog   color   os   io   2014   
原文地址：http://blog.csdn.net/rowanhaoa/article/details/24790105

上一篇：QQ 聊天机器人API

下一篇：不逃离WIndows，Asp.Net就只能写写进销存管理系统

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：usaco-3.1-PROB Shaping Regions-漂浮法
文章链接：http://soscw.com/essay/21802.html

亲，登录后才可以留言！

usaco-3.1-PROB Shaping Regions-漂浮法

评论

热门文章

推荐文章

最新文章

置顶文章