[ 模板 ] 求凸包面积

标签：return Point int double top 面积 const 求凸包 模板

先求凸const int N=1e6;

struct Point
{
    double x,y;
    double operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
};
Point stackk[N];    //凸包中所有点,下标从0....top开始 
Point p[N];            //存入的所有点 
Point MinA;
int top;
double dist(Point A,Point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转  =0共线 
double cross(Point A,Point B,Point C)    
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
 
bool cmp(Point a,Point b)    //极角排序 
{
    double k=cross(MinA,a,b);
    if(k>0) return 1;
    if(k<0) return 0;
    return dist(MinA,a)<dist(MinA,b);
}
void Graham(int n)
{
    int i;
    for(i=1; i<n; i++)
        if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
            swap(p[i],p[0]);
    MinA=p[0];
    sort(p+1,p+n,cmp);
    stackk[0]=p[0];
    stackk[1]=p[1];
    top=1;
    for(i=2; i<n; i++)
    {
        while(cross(stackk[top-1],stackk[top],p[i])<=0&&top>=1) --top;
        stackk[++top]=p[i];
    }
    top++;
}
int n,q;
double CalcArea(Point p[],int n)
{
    double  res = 0;
    for(int i = 0; i < n; i++)
        res += (p[i]^p[(i+1)%n])/2.0;
    return fabs(res);
}

 

标签：return,Point,int,double,top,面积,const,求凸包,模板
From： https://www.cnblogs.com/liyishui2003/p/16583753.html