计算几何Andrew法凸包

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

利用一下叉积和栈

int Andrew(D*R,int n,D*A){
    int m=0;
    sort(R+1,R+n+1);//for(int i=1;i<=n;i++)cout<<R[i].x<<" "<<R[i].y<<endl;
    for(int i=1;i<=n;i++){
        while(m>=2 && Cross(A[m]-A[m-1],R[i]-A[m-1])<=0)m--;
        A[++m]=R[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--){
        while(m>k  && Cross(A[m]-A[m-1],R[i]-A[m-1])<=0)m--;
        A[++m]=R[i];
    }
    return n>1?m-1:m;
}