把点集凸包Granham-Scan算法（使用水平序）.doc

《把点集凸包Granham-Scan算法（使用水平序）.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、把点集凸包化Granham-Scan算法（使用水平序）#include#include#include#includeusingnameaacestd;constintM=100000+5;structPoint{doublex,y;}p[M];doubledis(PointA,PointB){returnsqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));}boolcmp(Pointa,Pointb){if(a.x

2、.x>b.x)returnfalse;if(a.y

3、p+1,p+1+n,cmp);for(t=0,i=1;i<=n;i++){//合并排序if(i>1&&p[i].x==p[i-1].x&&p[i].y==p[i-1].y)continue;p[++t]=p[i];}n=t;t=0;memset(bo+1,true,n*sizeof(bo[0]));if(n>0){stack[++t]=1;bo[stack[t]]=false;}if(n>1){stack[++t]=2;bo[stack[t]]=false;}if(n>2){for(i=3;i

4、tack[t]],p[i])>=0)stack[++t]=i,bo[i]=false;else{while(t>=2&&Xdet(p[stack[t-1]],p[stack[t]],p[i])<0)bo[stack[t]]=true,t--;stack[++t]=i;bo[stack[t]]=false;}for(i=n;i>=1;i--)if(bo[i]&&Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0)stack[++t]=i,bo[i]=false;else{while(t>=2&&Xdet(p[stack[t-1]],p[stac

5、k[t]],p[i])<0)bo[stack[t]]=true,t--;stack[++t]=i;bo[stack[t]]=false;}t--;}for(i=1;i<=t;i++)pp[i]=p[stack[i]];memcpy(p+1,pp+1,t*sizeof(Point));n=t;}求凸点集的面积doublearea(Point*p,intn){doublesum=0;inti;p[n+1]=p[1];for(i=1;i<=n;i++)sum+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;returnsum/2.0;}constdouble

6、EPS=1e-9;constdoublemaxn=1e6-1;constdoublePI=acos(-1.);constintM=100+5;constdoubleoffset=11213;#definezero(x)(((x)>0?(x):-(x))

7、;}doublemultiply(Pointa,Pointb,Pointc){return(a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}doubledotmultiply(Pointa,Pointb,Pointc){return(a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);}boolonline(LINESEGL,Pointq){returnfabs(multiply(L.ed,q,L.st))