随笔-141  评论-9  文章-3  trackbacks-0
上浮法 + 矩阵分割

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

/*
ID: lorelei3
TASK: rect1
LANG: C++
*/


#include 
<fstream>
#include 
<iostream>

using namespace std;

const int MAX = 10010;
const int MAXC = 2510;

int N;
int x1[MAX], y1[MAX], x2[MAX], y2[MAX], color[MAXC], area[MAXC];

void cover(int lx, int ly, int rx, int ry, int c, int k){

    
while(k<=&&(    lx >= x2[k] ||
                    rx 
<= x1[k] ||
                    ly 
>= y2[k] ||
                    ry 
<= y1[k] ))
        k
++;
    
if(k>N){ area[c] += (ry-ly) * (rx-lx); return; }
    
if(lx<x1[k]) { cover(lx, ly, x1[k], ry, c, k+1); lx=x1[k]; }
    
if(rx>x2[k]) { cover(x2[k], ly, rx, ry, c, k+1); rx=x2[k]; }
    
if(ly<y1[k]) { cover(lx, ly, rx, y1[k], c, k+1); ly=y1[k]; }
    
if(ry>y2[k]) { cover(lx, y2[k], rx, ry, c, k+1); ry=y2[k]; }
}


int main(){

    
int i;

    ifstream fin(
"rect1.in");
    ofstream fout(
"rect1.out");

    fin
>>x2[0]>>y2[0]>>N;

    x1[
0]=0
    y1[
0]=0
    color[
0]=1;

    
for(i=1; i<=N; ++i)
        fin
>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>color[i];

    
for(i=N; i>=0; i--)
        cover(x1[i], y1[i], x2[i], y2[i], color[i], i
+1);

    
for(i=0; i<MAXC; ++i)
        
if(area[i])
            fout
<<i<<" "<<area[i]<<endl;

    
return 0;
}
posted on 2010-12-16 15:41 小阮 阅读(214) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理