恶心死的题目，暴力法超时超空间。

思路：

从最上面一层（N）到第一层（0，白色层）开始分析着色的rect，使用cut函数

思路是第i层的rect和他上面的所有rect进行对比， 如果本层的rect遇到有一部分被上层的rect覆盖，就把覆盖掉的部分给去掉；直到最后的部分是没有被覆盖的，就将其记载；

/* ID: wangxin12 PROG: rect1LANG: C++ */ #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct rect {	int x1, y1, x2, y2, color;	rect(int lx, int ly, int rx, int ry, int c) {		x1 = lx; y1 = ly; x2 = rx; y2 = ry; color = c; 	}	rect() { }	void reset(int lx, int ly, int rx, int ry, int c) {		x1 = lx; y1 = ly; x2 = rx; y2 = ry; color = c; 	}};int A, B, N; //1 <= A,B <= 10000; N <= 1000int colors[2501];  // color <= 2500;rect rects[1001];int cut(int x1, int y1, int x2, int y2, int index) {	while(index <= N && 		(x1 >= rects[index].x2 ||		y1 >= rects[index].y2 ||		x2 <= rects[index].x1 ||		y2 <= rects[index].y1))      //和第index个着色rect没有相交		index++; //继续和下一个rect进行比较	if(x1 == x2 || y1 == y2) return 0;	if(index > N) return (x2 - x1) * (y2 - y1);	//有第index个rect相交，进行切割	int ans = 0;	if(x1 < rects[index].x1) {		ans += cut(x1, y1, rects[index].x1, y2, index );		x1 = rects[index].x1;	}	if(x2 > rects[index].x2) {		ans += cut(rects[index].x2, y1, x2, y2, index );		x2 = rects[index].x2;	}	if(y1 < rects[index].y1) {		ans += cut(x1, y1, x2, rects[index].y1, index );		y1 = rects[index].y1;	}	if(y2 > rects[index].y2) {		ans += cut(x1, rects[index].y2, x2, y2, index );		y2 = rects[index].y2;	}	return ans;}int main() {	ifstream fin("rect1.in");	ofstream fout("rect1.out");		int i, j;	fin>>A>>B>>N;	rects[0].reset(0, 0, A, B, 1); //white paper	for(i = 1; i <= N; i++) {		int x1, y1, x2, y2, c;		fin>>x1>>y1>>x2>>y2>>c;		rects[i].reset(x1, y1, x2, y2, c);	}		memset(colors, 0, sizeof(colors));	for(i = N; i >= 0; i--) {		colors[rects[i].color] += cut(rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2, i + 1);	}	for(j = 1; j <= 2500; j++) {		if(colors[j] > 0)			fout<
         
          <<" "<
          
           <
          
         
        
       
      
     
    

描述

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 32 2 18 18 20 8 19 19 38 0 10 19 4

.......

[]SAMPLE OUTPUT

1 912 843 1874 38

[]INPUT EXPLANATION

请注意：被(0,0)和(2,2)所描绘的是2个单位宽、2个单位高的区域

这里有一个示意图输入：

1111111111111111111133333333443333333331333333334433333333313333333344333333333133333333443333333331333333334433333333313333333344333333333133333333443333333331333333334433333333313333333344333333333133333333443333333331333333334433333333311122222244222222221111222222442222222211112222224422222222111122222244222222221111222222442222222211112222224422222222111111111144111111111111111111441111111111

'4'在(8,0)与(10,19)形成的是宽为2的区域,而不是3.（也就是说，4形成的区域包含(8,0)和(8,1) ，而不是(8,0)和(8,2)） 。