给出若干个点，求出它们的凸包，并且按原点为第一点的逆时针方向输出。
(0,0) (-30,-40) (-30,-50) (-10,-60) (50,-60) (70,-50) (90,-20) (90,10) (80,20) (60,30)
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include< set> 7 #include<map> 8 #include<queue> 9 #include<vector> 10 #include< string> 11 #define Min(a,b) a<b?a:b 12 #define Max(a,b) a>b?a:b 13 #define CL(a,num) memset(a,num,sizeof(a)); 14 #define maxn 60 15 #define eps 1e-12 16 #define inf 100000000 17 #define mx 1<<60 18 #define ll __int64 19 using namespace std; 20 struct point 21 { 22 double x,y; 23 }p[maxn]; 24 int res[maxn]; 25 int dblcmp( double x) 26 { 27 if(fabs(x) < eps) return 0; 28 if(x < 0) return - 1; 29 else return 1; 30 } 31 double det( double x1, double y1, double x2, double y2) 32 { 33 return x1*y2 - x2*y1 ; 34 } 35 double cross(point a, point b, point c) 36 { 37 return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); 38 } 39 int cmp(point a,point b) 40 { 41 if(a.y != b.y) return a.y < b.y; 42 else return a.x < b.x; 43 } 44 int top ,n; 45 void graham() 46 { 47 int i,len; 48 top = 0; 49 sort(p,p+n,cmp); 50 51 if(n == 0) return ;res[top++] = 0; 52 if(n == 1) return ;res[top++] = 1; 53 54 for(i = 2 ;i<n;i++) // 求右链 55 { 56 while(top&&dblcmp(cross(p[res[top - 1]],p[res[top - 2]],p[i])) > 0) top--; 57 58 res[top++] = i; 59 } 60 61 len = top ; 62 63 for(i = n - 2;i >= 0;i--) // 求左链 64 { 65 while(top != len && dblcmp(cross(p[res[top - 1]],p[res[top - 2]],p[i])) > 0)top--; 66 res[top++] = i; 67 68 } 69 top--;//第一个点 入栈两次 所以 减 1； 70 71 } 72 int main() 73 { 74 75 n = 0; 76 int i,s; 77 // freopen("data.txt","r",stdin); 78 while(scanf( " %lf%lf ",&p[n].x,&p[n].y)!=EOF)n++; 79 graham() ; 80 81 for(s = 0 ; s < top;s++) 82 { 83 if(p[res[s]].x == 0&&p[res[s]].y == 0) { break;} 84 } 85 for( i = s ; i < top; i++) 86 { 87 printf( " (%.0lf,%.0lf)\n ",p[res[i]].x,p[res[i]].y); 88 } 89 for(i = 0 ; i< s;i++) 90 { 91 printf( " (%.0lf,%.0lf)\n ",p[res[i]].x,p[res[i]].y); 92 } 93 94 }