superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 3.1- Shaping Regions

Posted on 2009-04-27 10:53 superman 阅读(113) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理