poj 1696

不错的一题，需要极角排序，看了别人的代码做的。。。。。。计算几何啊~~~
View Code
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 const double er = 1e-8;
 7 struct point
 8 {
 9     int index;
10     int x,y;
11 }p[100];
12 int n;
13 int res;
14 
15 int dis(point a,point b)
16 {
17     return sqrt(1.0*(a.x - b.x) * (a.x - b.x) + 1.0*(a.y - b.y)*(a.y - b.y));
18 }
19 
20 double outer_product(point a,point b,point c)
21 {
22     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x-a.x);
23 }
24 
25 bool cmp(point a,point b)
26 {
27     double temp = outer_product(p[res - 1],a,b);
28     if(temp > er) return true;
29     temp = temp > 0?temp:(-temp);
30     if(temp < er&&dis(a,p[res - 1]) < dis(b,p[res -1]))
31         return true;
32     return false;
33 }
34 
35 int main()
36 {
37     int cas;
38     scanf("%d",&cas);
39     while(cas --)
40     {
41         scanf("%d",&n);
42         for(int i = 0;i < n;i ++)
43         {
44             scanf("%d%d%d",&p[i].index,&p[i].x,&p[i].y);
45             if(p[i].y < p[0].y) std::swap(p[i],p[0]);
46             if(p[i].y == p[0].y)
47             {
48                 if(p[i].x <p[0].x)
49                     std::swap(p[i],p[0]);
50             }
51         }
52         printf("%d %d",n,p[0].index);
53 
54         for(res = 1;res < n;res ++)
55         {
56             std::sort(p+res,p+n,cmp);
57             printf(" %d",p[res].index);
58         }
59         printf("\n");
60     }
61 
62     return 0;
63 }