Posted on 2008-04-09 19:52
superman 閱讀(422)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1197 C++ 00:00.00 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 struct { int x1, y1, x2, y2, match; } slide[26];
7 struct { int x, y; bool matched; } p[26];
8
9 int n;
10
11 bool s1()
12 {
13 for(int i = 0; i < n; i++)
14 if(slide[i].match == -1)
15 {
16 int cnt = 0, idx;
17 for(int j = 0; j < n; j++)
18 if(p[j].matched == false)
19 if(slide[i].x1 <= p[j].x && p[j].x <= slide[i].x2)
20 if(slide[i].y1 <= p[j].y && p[j].y <= slide[i].y2)
21 {
22 cnt++;
23 idx = j;
24 if(cnt > 1)
25 break;
26 }
27 if(cnt == 1)
28 {
29 slide[i].match = idx;
30 p[idx].matched = true;
31 return true;
32 }
33 }
34 return false;
35 }
36
37 bool s2()
38 {
39 for(int i = 0; i < n; i++)
40 if(p[i].matched == false)
41 {
42 int cnt = 0, idx;
43 for(int j = 0; j < n; j++)
44 if(slide[j].match == -1)
45 if(slide[j].x1 <= p[i].x && p[i].x <= slide[j].x2)
46 if(slide[j].y1 <= p[i].y && p[i].y <= slide[j].y2)
47 {
48 cnt++;
49 idx = j;
50 if(cnt > 1)
51 break;
52 }
53 if(cnt == 1)
54 {
55 p[i].matched = true;
56 slide[idx].match = i;
57 return true;
58 }
59 }
60 return false;
61 }
62
63 int main()
64 {
65 int Heap = 0;
66 while((cin >> n) && n)
67 {
68 for(int i = 0; i < n; i++)
69 {
70 slide[i].match = -1;
71 cin >> slide[i].x1 >> slide[i].x2 >> slide[i].y1 >> slide[i].y2;
72 }
73 for(int i = 0; i < n; i++)
74 {
75 p[i].matched = false;
76 cin >> p[i].x >> p[i].y;
77 }
78
79 int m = 0;
80 while(s1())m++;
81 while(s2())m++;
82
83 cout << "Heap " << ++Heap << endl;
84
85 if(m == 0)
86 cout << "none" << endl;
87 else
88 {
89 while(m)
90 for(int i = 0; i < n; i++)
91 if(slide[i].match != -1)
92 {
93 cout << '(' << char(i + 'A') << ',' << slide[i].match + 1 << ')';
94 cout << (--m == 0 ? '\n' : ' ');
95 }
96 }
97 cout << endl;
98 }
99
100 return 0;
101 }
102