Posted on 2009-04-27 10:53
superman 閱讀(133)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m, t;
6 int sx[1001], sy[1001], tx[1001], ty[1001], col[1001], cnt[2600];
7
8 int curCol;
9 void cut(int csx, int csy, int ctx, int cty, int i)
10 {
11 while ((i <= t) && (sx[i] >= ctx || tx[i] <= csx || sy[i] >= cty || ty[i] <= csy))
12 i++;
13 if (i > t)
14 {
15 cnt[curCol] += (ctx - csx) * (cty - csy);
16 return;
17 }
18
19 if (csx < sx[i])
20 {
21 cut(csx, csy, sx[i], cty, i + 1);
22 csx = sx[i];
23 }
24 if (ctx > tx[i])
25 {
26 cut(tx[i], csy, ctx, cty, i + 1);
27 ctx = tx[i];
28 }
29 if (csy < sy[i])
30 cut(csx, csy, ctx, sy[i], i + 1);
31 if (cty > ty[i])
32 cut(csx, ty[i], ctx, cty, i + 1);
33 }
34
35 int main()
36 {
37 freopen("rect1.in", "r", stdin);
38 freopen("rect1.out", "w", stdout);
39
40 cin >> n >> m >> t;
41
42 sx[0] = 0;
43 sy[0] = 0;
44 tx[0] = n;
45 ty[0] = m;
46 col[0] = 1;
47 for (int i = 1; i <= t; i++)
48 cin >> sx[i] >> sy[i] >> tx[i] >> ty[i] >> col[i];
49
50 for (int i = t; i >= 0; i--)
51 {
52 curCol = col[i];
53 cut(sx[i], sy[i], tx[i], ty[i], i + 1);
54 }
55
56 for (int i = 1; i <= 2500; i++)
57 if (cnt[i])
58 cout << i << ' ' << cnt[i] << endl;
59
60 return 0;
61 }
62