又有好长时间没写了解题报告了，保研总算搞定了，月底去武汉，磨枪中....
1 /*
2 * SOUR:pku 1696
3 * ALGO:computional geometry
4 * DATE: Tue, 13 Oct 2009 10:42:25 +0800
5 * COMM:3
6 * 叉积点积转啊转啊
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 #include<cmath>
14 using namespace std;
15 typedef long long LL;
16 const int maxint = 0x7fffffff;
17 const long long max64 = 0x7fffffffffffffffll;
18 #define pr(x
) fprintf(stderr, x)
19 /* #define pr(x) for(;0;) */
20 const int N = 128;
21 struct point_t {
22 int x, y, idx;
23 point_t() {
24 } point_t(int a, int b) {
25 x = a, y = b;
26 }
27 } p[N], st[N];
28
29 bool vis[N];
30
31 #define sqr(x) ((x)*(x))
32 double dist(point_t a)
33 { return sqrt(sqr(a.x) + sqr(a.y)); }
34 double dist(point_t a, point_t b)
35 { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
36
37 point_t operator +(point_t a, point_t b)
38 { return point_t(a.x + b.x, a.y + b.y); }
39 point_t operator -(point_t a, point_t b)
40 { return point_t(a.x - b.x, a.y - b.y); }
41
42 int cross_mul(point_t a, point_t b)
43 { return a.x * b.y - a.y * b.x; }
44 int cross_mul(point_t a, point_t b, point_t c)
45 { return cross_mul(a - c, b - c); }
46 int dot_mul(point_t a, point_t b)
47 { return a.x * b.x + a.y * b.y; }
48 int dot_mul(point_t a, point_t b, point_t c)
49 { return dot_mul(a - c, b - c); }
50
51 double angle(point_t a, point_t b)
52 {
53 double val = dot_mul(a, b);
54 val /= dist(a);
55 val /= dist(b);
56 return val;
57 }
58
59 int n, idx, top;
60 const int inf = (1 << 29);
61 void graham()
62 {
63 int i, j, k;
64 memset(vis, 0, sizeof(vis));
65 top = 2, st[0] = p[0], st[1] = p[1];
66 vis[0] = vis[1] = true;
67 for (i = 2; i <= n; i++) {
68 double val = -inf;
69 int idx;
70 for (j = 2; j <= n; j++) {
71 if (!vis[j]) {
72 int c = cross_mul(st[top - 1], p[j], st[top - 2]);
73 double d = angle(st[top - 1] - st[top - 2], p[j] - st[top - 1]);
74 if (c > 0) {
75 if ((d > val) || (d == val && dist(p[j], st[top - 1]) < dist(p[idx], st[top - 1]))) {
76 idx = j;
77 val = d;
78 }
79 }
80 }
81 }
82 if (val == -inf)
83 break;
84 st[top++] = p[idx], vis[idx] = true;
85 }
86 }
87
88 int main()
89 {
90 int i, j, k, testid;
91 scanf("%d", &testid);
92 while (testid-- > 0) {
93 scanf("%d", &n);
94 idx = 1;
95 scanf("%d%d%d", &p[1].idx, &p[1].x, &p[1].y);
96 for (i = 2; i <= n; i++) {
97 scanf("%d%d%d", &p[i].idx, &p[i].x, &p[i].y);
98 if ((p[i].y < p[idx].y) || (p[i].y == p[idx].y && p[i].x < p[idx].x)) {
99 idx = i;
100 }
101 }
102 swap(p[1], p[idx]);
103 p[0].idx = 0, p[0].x = 0, p[0].y = p[1].y;
104 graham();
105 printf("%d", top - 1);
106 for (i = 1; i < top - 1; i++) {
107 printf(" %d", st[i].idx);
108 }
109 printf(" %d\n", st[i].idx);
110 }
111 return 0;
112 }
113