? 漂浮法：从最上面的矩形开始向下求它颜色的面积 ，直到最下面的大矩形。对每一个矩形，从其位置上浮，碰到在它上面的矩形，它就分裂成几个小矩形，递归模拟上浮过程。
??????? 好像某年有个亚洲区的题和这个很像，在屏幕上的矩形的覆盖，不过那个题最多有26个矩形，可以暴力求解，比这个还简单了。
?01 /*?
02 ID:jzzlee1?
03 PROB:rect1?
04 LANG:C++?
05 */
06 //#include
07 #include
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< 66? }? 67? int main()? www.2cto.com 68? {? 69????? work();? 70????? return 0;? 71? }