首页 > 代码库 > 二维凸包模板
二维凸包模板
double cross(Point a,Point b){ return a.x*b.y-a.y*b.x;}double mul(Point p0,Point p1,Point p2){ return cross(p1-p0,p2-p0);}double dis(Point a){ return sqrt(a.x*a.x+a.y*a.y);}bool cmp(Point a,Point b){ if(dcmp(mul(p[0],a,b))==0) return dis(a-p[0])<dis(b-p[0]); else return dcmp(mul(p[0],a,b))>0;}int Graham(int n){ int i,k = 0,top; Point tmp; 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; } if(k!=0) { tmp = p[0]; p[0] = p[k]; p[k] = tmp; } sort(p+1,p+n,cmp); ch[0] = p[0]; ch[1] = p[1]; top = 1; for(i = 2; i < n ; i++) { while(top>0&&dcmp(mul(ch[top-1],ch[top],p[i]))<0) top--; top++; ch[top] = p[i]; } return top;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。