计算几何Graham法凸包

This article is made by Jason-Cow.
Welcome to reprint.
But please post the article's address.

关键一句话

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

附加，极角排序，课上讲~~

 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 }

学了Andrew后，觉得Graham好丑，而且常数还大

唯一的好处是好写，其实差不多

~~Jason_liu O(∩_∩)O