格雷厄姆扫描法解凸壳问题

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 
 7 struct point
 8 {
 9     double x;
10     double y;
11     double angle;
12 };
13 //判断点A，D是否在点B，C连线的两侧
14 bool different(point A,point B,point C,point D)
15 {
16     double x1=A.x,x2=B.x,x3=C.x,x4=D.x;
17     double y1=A.y,y2=B.y,y3=C.y,y4=D.y;
18     if(x3==x2)
19     {
20         if((x1-x2)*(x4-x2)<0)
21             return true;
22         else 
23             return false;
24     }
25     else
26     {
27         if((((x1-x2)*(y3-y2)+y2*(x3-x2))/(x3-x2))*(((x4-x2)*(y3-y2)+y2*(x3-x2))/(x3-x2))<0)
28             return true;
29         else return false;
30     }    
31 }
32 double my_angle(point A,point B)
33 {
34     if(A.x==B.x && A.y==B.y)
35         return 0;
36     return acos((B.x-A.x)/(sqrt((B.y-A.y)*(B.y-A.y)+(B.x-A.x)*(B.x-A.x))));
37 }
38 bool ismin(point A,point B)
39 {
40     return A.y<B.y;
41 }
42 bool isAngle(point A,point B)
43 {
44     return A.angle<B.angle;
45 }
46 int main()
47 {
48     vector<point> num;
49     int x,y;
50     char c;
51     while(cin>>x>>y)
52     {
53         point temp;
54         temp.x=x;
55         temp.y=y;
56         temp.angle=0;
57         num.push_back(temp);
58         cin.get(c);
59         if(c=='
')
60             break;
61     }
62     sort(num.begin(),num.end(),ismin);
63     point first=num[0];
64     for(vector<point>::iterator iter=num.begin();iter!=num.end();iter++)
65     {
66         (*iter).angle=my_angle(first,*iter);
67     }
68     sort(num.begin(),num.end(),isAngle);
69     vector<point> result;
70     result.push_back(num[0]);
71     result.push_back(num[1]);
72     for(int i=2;i<num.size()-1;i++)
73     {
74         if(!different(num[i-2],num[i-1],num[i],num[i+1]))
75             result.push_back(num[i]);
76     }
77     result.push_back(num[num.size()-1]);
78     for(int p=0;p<result.size();p++)
79     {
80         cout<<result[p].x<<" "<<result[p].y<<endl;
81     }
82     system("pause");
83     return 0;
84 }