poj 1696:Space Ant（计算几何，凸包变种，极角排序）

 1 #include <iostream>
 2 using namespace std;
 3 #define eps 1e-10
 4 struct Point{    //定义点
 5     double x,y;
 6     Point(double x=0,double y=0):x(x),y(y) {}
 7 };
 8 typedef Point Vector;    //重定义向量
 9 Vector operator + (Vector a,Vector b)    //向量+向量
10 {
11     return Vector(a.x+b.x,a.y+b.y);
12 }
13 Vector operator - (Point a,Point b)    //点-点 = 向量
14 {
15     return Vector(a.x-b.x,a.y-b.y);
16 }
17 double Cross(Vector a,Vector b)    //求叉积
18 {
19     return a.x*b.y-b.x*a.y;
20 }
21 int main()
22 {
23     int T;
24     cin>>T;
25     while(T--){
26         int n,i;
27         Point p[55];
28         bool isw[55] = {0};    //记录走没走过
29         cin>>n;
30         for(i=1;i<=n;i++){    //输入点集
31             int t;
32             cin>>t;
33             cin>>p[t].x>>p[t].y;
34         }
35         //找出y坐标最小的那个点
36         double yMin=p[1].y;
37         int num = 1;
38         for(i=2;i<=n;i++){
39             if(p[i].y < yMin){
40                 yMin = p[i].y;
41                 num = i;
42             }
43         }
44         //构成凸包
45         int pl[55];    //存储结果
46         int j;
47         pl[1] = num;
48         isw[pl[1]] = true;
49         for(i=1;i<n;i++){
50             for(j=1;j<=n;j++)    //选择一个没走过的点
51                 if(!isw[j])
52                     break;
53             pl[i+1] = j;
54             for(j=1;j<=n;j++){    //选择最右边的点
55                 if(pl[i+1]==j || isw[j])
56                     continue;
57                 if(Cross(p[j] - p[pl[i]],p[pl[i+1]] - p[pl[i]])>0)
58                     pl[i+1] = j;
59             }
60             isw[pl[i+1]] = true;
61         }
62         cout<<n<<‘ ‘;
63         for(i=1;i<=n;i++)
64             cout<<pl[i]<<‘ ‘;
65         cout<<endl;
66     }
67     return 0;
68 }