USACO3.1 Shaping Regions(rect1)

  漂浮法：从最上面的矩形开始向下求它颜色的面积 ，直到最下面的大矩形。对每一个矩形，从其位置上浮，碰到在它上面的矩形，它就分裂成几个小矩形，递归模拟上浮过程。
        好像某年有个亚洲区的题和这个很像，在屏幕上的矩形的覆盖，不过那个题最多有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  }