首页 > 代码库 > 凸包模板

凸包模板

struct point{    double x,y,angel;} p[N],stack[N];int top,n;double dis(point a,point b)//求距离{    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool mult(point p1,point p2,point p0)//叉乘{    return (p1.x-p0.x)*(p2.y-p0.y) >= (p2.x-p0.x)*(p1.y-p0.y);}bool cmp(point a,point b){    if(a.angel == b.angel)    {        if (a.x == b.x)            return a.y > b.y;        return a.x > b.x;    }    return a.angel < b.angel;}void graham(){//p为点集,n为点的个数,stack为凸包点集,top为凸包个数    int i,k=0;    point temp;    for(i=0; i<n; i++)        if(p[i].y<p[k].y||((p[i].y==p[k].y)&&(p[i].x<p[k].x)))            k=i;    temp=p[0];    p[0]=p[k];    p[k]=temp;    for(i=1; i<n; i++)        p[i].angel=atan2(p[i].y-p[0].y,p[i].x-p[0].x);    sort(p+1,p+n,cmp);    stack[0]=p[0];    stack[1]=p[1];    stack[2]=p[2];    top=3;    for(i=3; i<n; i++)    {        while(top > 2 && mult(stack[top-2],stack[top-1],p[i])<=0)            top--;        stack[top++]=p[i];    }}
View Code