Posted on 2008-04-10 23:00
superman 閱讀(274)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1179 C++ 00:00.00 848K */
2 #include <string>
3 #include <stdlib.h>
4 #include <iostream>
5 #include <algorithm>
6
7 using namespace std;
8
9 struct point { int x, y; char letter; } p[26];
10
11 int cmp(const void * a, const void * b)
12 {
13 point * c = (point *) a;
14 point * d = (point *) b;
15 if(c -> x == d -> x)
16 return c -> y - d -> y;
17 return c -> x - d -> x;
18 }
19
20 int main()
21 {
22 int n, set = 0;
23 while((cin >> n) && n)
24 {
25 for(int i = 0; i < n; i++)
26 cin >> p[i].letter >> p[i].x >> p[i].y;
27
28 qsort(p, n, sizeof(point), cmp);
29
30 string rec[1000]; int m = 0;
31 for(int i = 0; i < n; i++)
32 for(int j = i + 1; j < n; j++)
33 {
34 int a = -1, b = -1;
35 for(int k = i + 1; k < n; k++)
36 if(p[k].x == p[i].x && p[k].y == p[j].y)
37 {
38 a = k;
39 break;
40 }
41 for(int k = i + 1; k < n; k++)
42 if(p[k].x == p[j].x && p[k].y == p[i].y)
43 {
44 b = k;
45 break;
46 }
47 if(a != -1 && b != -1)
48 {
49 rec[m] += p[a].letter;
50 rec[m] += p[j].letter;
51 rec[m] += p[b].letter;
52 rec[m] += p[i].letter;
53 m++;
54 }
55 }
56 sort(rec, rec + m);
57
58 cout << "Point set " << ++set << ':';
59 if(m == 0)
60 cout << " No rectangles";
61 else
62 {
63 cout << endl;
64 for(int i = 0; i < m; i++)
65 {
66 cout << ' ' << rec[i];
67 if(i + 1 != m && (i + 1) % 10 == 0)
68 cout << endl;
69 }
70 }
71 cout << endl;
72 }
73
74 return 0;
75 }
76