上浮法 + 矩阵分割
以逆序来进行放置，即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<=N &&( 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
小阮 阅读(201)
评论(0) 编辑 收藏 引用 所属分类:
USACO