1 #include<stdio.h> 2 #include<math.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 const int MAXN=105; 7 8 struct point 9 { 10 int x,y; 11 }; 12 point list[MAXN],list2[MAXN]; 13 int stack[MAXN],top; 14 15 int cross(point p0,point p1,point p2) //计算叉积 p0p1 X p0p2 16 { 17 return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); 18 } 19 double dis(point p1,point p2) //计算 p1p2的 距离 20 { 21 return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); 22 } 23 bool cmp(point p1,point p2) //极角排序函数 ， 角度相同则距离小的在前面 24 { 25 int tmp=cross(list[0],p1,p2); 26 if(tmp>0) return true; 27 else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true; 28 else return false; 29 } 30 void init(int n) //输入，并把 最左下方的点放在 list[0] 。并且进行极角排序 31 { 32 int i,k; 33 point p0; 34 scanf("%d%d",&list[0].x,&list[0].y); 35 p0.x=list[0].x; 36 p0.y=list[0].y; 37 k=0; 38 for(i=1;i<n;i++) 39 { 40 scanf("%d%d",&list[i].x,&list[i].y); 41 if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) ) 42 { 43 p0.x=list[i].x; 44 p0.y=list[i].y; 45 k=i; 46 } 47 } 48 list[k]=list[0]; 49 list[0]=p0; 50 51 sort(list+1,list+n,cmp); 52 } 53 54 void graham(int n) 55 { 56 int i; 57 if(n==1) {top=0;stack[0]=0;} 58 if(n==2) 59 { 60 top=1; 61 stack[0]=0; 62 stack[1]=1; 63 } 64 if(n>2) 65 { 66 for(i=0;i<=1;i++) stack[i]=i; 67 top=1; 68 69 for(i=2;i<n;i++) 70 { 71 while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<=0) top--; 72 top++; 73 stack[top]=i; 74 } 75 } 76 }
转自某位大神的模版http://www.cnblogs.com/kuangbin/archive/2012/09/29/2707961.html