计算几何-Graham法-凸包

Cross(A[m-1]-R[i],A[m]-R[i])<=0

 1 D O;
 2 bl acomp(D A,D B){
 3     db x=Cross(A-O,B-O);
 4     if(x>0)return 1;if(x<0)return 0;
 5     return Dis(O,A)<Dis(O,B);
 6 }
 7 
 8 int Graham(D*R,int n,D*A){
 9     for(int i=1;i<=n;i++)
10         if(R[i].y<R[1].y||(R[i].y==R[1].y&&R[i].x<R[1].x))swap(R[i],R[1]);
11     O=R[1],sort(R+2,R+n+1,acomp);
12     int m=0;A[++m]=R[1],A[++m]=R[2];
13     for(int i=3;i<=n;i++){
14         while(m>1 && Cross(A[m-1]-R[i],A[m]-R[i])<=0)m--;
15         A[++m]=R[i];
16     }
17     return m;
18 }