漂浮法：從最上面的矩形開始向下求它顏色的面積 ，直到最下面的大矩形。對每一個矩形，從其位置上浮，碰到在它上面的矩形，它就分裂成幾個小矩形，遞歸模擬上浮過程。
好像某年有個亞洲區的題和這個很像，在屏幕上的矩形的覆蓋，不過那個題最多有26個矩形，可以暴力求解，比這個還簡單了。
01 /*
02 ID:jzzlee1
03 PROB:rect1
04 LANG:C++
05 */
06 //#include<iostream>
07 #include<fstream>
08 using namespace std;
09 ifstream cin("rect1.in");
10 ofstream cout("rect1.out");
11 long int x1[1010],y1[1010],x2[1010],y2[1010],ans[2510],c[2510];
12 int n,maxc;
13 void color(int l,int r,int s,int d,int k,int col)
14 {
15 while( (k<=n)&&((l>=x2[k])||(r<=x1[k])||(d<=y1[k])||s>=y2[k]) )
16 k++;
17 if( k>n )
18 {
19 ans[col]+=(r-l)*(d-s);
20 return;
21 }
22 else
23 {
24 if(l<=x1[k])
25 {
26 color(l,x1[k],s,d,k+1,col);
27 l=x1[k];
28 }
29 if(r>=x2[k])
30 {
31 color(x2[k],r,s,d,k+1,col);
32 r=x2[k];
33 }
34 if(s<=y1[k])
35 {
36 color(l,r,s,y1[k],k+1,col);
37 s=y1[k];
38
39 }
40 if(d>=y2[k])
41 {
42 color(l,r,y2[k],d,k+1,col);
43 d=y2[k];
44 }
45 }
46 }
47 void work()
48 {
49 int i,j;
50 cin>>x2[0]>>y2[0]>>n;
51 x1[0]=0;
52 y1[0]=0;
53 c[0]=1;
54 maxc=0;
55 for(i=1;i<=n;i++)
56 {
57 cin>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>c[i];
58 if(c[i]>maxc)
59 maxc=c[i];
60 }
61 for(i=n;i>=0;i--)
62 color(x1[i],x2[i],y1[i],y2[i],i+1,c[i]);
63 for(i=1;i<=maxc;i++)
64 if(ans[i]!=0)
65 cout<<i<<" "<<ans[i]<<endl;
66 }
67 int main() www.2cto.com
68 {
69 work();
70 return 0;
71 }
