描述
N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张横宽为A竖长为B的白纸上。
这些长方形被放置时，保证了它们的边与白纸的边缘平行。 所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。
坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。
[编辑]格式
PROGRAM NAME: rect1
INPUT FORMAT:
(file
rect1.in)
按顺序输入放置长方形的方法。第一行输入的是那个放在底的长方形(即白纸)。
第 1 行: A ， B 和 N由空格分开 (1
<=A, B<=10,000)
第 2 到N+1行: 为五个整数 llx, lly, urx, ury,
color 这是一个长方形的左下角坐标，右上角坐标(x+1,y+1)和颜色。
颜色 1和底部白纸的颜色相同。 (1 <= color <=
2500)
OUTPUT FORMAT：
(file
rect1.out)
输出且仅输出所有能被看到颜色，和该颜色的总面积(可以由若干个不连通的色块组成)，按color增序排列。
[编辑]SAMPLE
INPUT
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
.......
[编辑]SAMPLE
OUTPUT
1 91
2 84
3 187
4 38
[编辑]INPUT EXPLANATION
请注意：被(0,0)和(2,2)所描绘的是2个单位宽、2个单位高的区域
这里有一个示意图输入：
11111111111111111111
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11111111441111111111
11111111441111111111
‘4‘在(8,0)与(10,19)形成的是宽为2的区域,而不是3.（也就是说，4形成的区域包含(8,0)和(8,1)
，而不是(8,0)和(8,2)） 。
分析：
方法一：漂浮法（好文艺的名字~~~~）
漂浮法的主要思想是将题目模拟的过程倒置，即从第n个矩形往第1个矩形倒着做，这样做有一个好处，就是每次处理完毕看到的就是最终的结果，因为挡着它的都已经在之前被处理过了，这位递归创造了条件。具体的，就是想象分成n层的海水，倒着枚举每一块矩形从最下面层漂浮到上面，如果中间碰到了某块矩形则这块漂浮中的矩形就会断裂，没挡到的继续上浮，挡到的就动不了了，这样一直飘到水面，就是最后你看到的，统计一下就行了。
具体的递归做法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void
cover(int
l,int
r,int
s,int
d,int
k,int
col)
{ while
((k<=n)&&(l>=x2[k]||r<=x1[k]||s>=y2[k]||d<=y1[k])) ++k;
if(k>n)
{
ans[col]+=(r-l)*(d-s);
return;
}
if(l<=x1[k]) cover(l,x1[k],s,d,k+1,col),l=x1[k];
if(r>=x2[k]) cover(x2[k],r,s,d,k+1,col),r=x2[k];
if(s<=y1[k]) cover(l,r,s,y1[k],k+1,col),s=y1[k];
if(d>=y2[k]) cover(l,r,y2[k],d,k+1,col),d=y2[k];
return;
} |
————————————————————————————————————————————————————————————
方法二：矩形切割
http://hi.baidu.com/oimaster/item/43dd1520adcfd6cda4275a42
这个做法是按顺序的，仔细想想发现方法一和方法二有异曲同工之妙……