首页 > 代码库 > 凸包模板
凸包模板
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]; }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。