hdu 1543 Paint the Wall

题意：有一面h*w的墙(0<h,w<=10000)，先后往墙上刷n个矩形，给出坐标和颜色c(1=<c<=100)，后刷的会覆盖先前刷的(如果重合)，求最后墙上剩下的颜色及对应面积。

由于矩形数量最多只有100个，所以离散化后可以暴力。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int M = 10005;
 8 const int N = 105;
 9 
10 struct Rec
11 {
12     int top, left, bottom, right, color;
13 }rec[N];
14 int Y[2*N], X[2*N], aa[2*N][2*N], ans[N], indexx, indexy, xx, yy;
15 
16 int main()
17 {
18     int Case = 1;
19     int h, w, n, top, left, bottom, right;
20     while(scanf("%d%d",&h,&w)!=EOF)
21     {
22         if(h==0 && w==0) break;
23 
24         map<int, int> mapx, mapy;
25         indexx = indexy = 0;
26         scanf("%d",&n);
27         for(int i=0; i<n; i++)
28         {
29             scanf("%d%d%d%d%d",&rec[i].top,&rec[i].left,&rec[i].bottom,&rec[i].right,&rec[i].color);
30             X[indexx++] = rec[i].left; X[indexx++] = rec[i].right;
31             Y[indexy++] = rec[i].top; Y[indexy++] = rec[i].bottom;
32         }
33         sort(X, X+indexx);
34         sort(Y, Y+indexy);
35         xx = 1;
36         for(int i=1; i<indexx; i++)
37             if(X[i]!=X[i-1])
38                 X[xx++] = X[i];
39         yy = 1;
40         for(int i=1; i<indexy; i++)
41             if(Y[i]!=Y[i-1])
42                 Y[yy++] = Y[i];
43         for(int i=0; i<xx; i++)
44             mapx[X[i]] = i;
45         for(int i=0; i<yy; i++)
46             mapy[Y[i]] = i;
47         memset(aa, 0, sizeof(aa));
48         for(int i=0; i<n; i++)
49         {
50             top = mapy[rec[i].top]; left = mapx[rec[i].left];
51             bottom = mapy[rec[i].bottom]; right = mapx[rec[i].right];
52             for(int j=top; j<bottom; j++)
53                 for(int k=left; k<right; k++)
54                     {aa[j][k] = rec[i].color;}
55         }
56         memset(ans, 0, sizeof(ans));
57         for(int i=0; i<yy-1; i++) //xx 与 yy换了位置，WA无数。。。
58             for(int j=0; j<xx-1; j++)
59             {
60                 int tempx1 = X[i], tempx2 = X[i+1], tempy1 = Y[j], tempy2 = Y[j+1];
61                 ans[aa[i][j]] += (tempx2 - tempx1) * (tempy2 - tempy1);
62             }
63         int sum = 0;
64         if(Case>1) printf("
");
65         printf("Case %d:
",Case++);
66         for(int i=1; i<=100; i++)
67         {
68             if(ans[i]>0)
69             {
70                 printf("%d %d
",i, ans[i]);
71                 sum++;
72             }
73         }
74         if(sum==1)
75             printf("There is %d color left on the wall.
",sum);
76         else
77             printf("There are %d colors left on the wall.
",sum);
78     }
79     return 0;
80 }