把点集凸包化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、eturntrue;if(a.x>b.x)returnfalse;if(a.y

3、把点集土包化n*log(n);{inti,t;sort(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=

4、3;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]=

5、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;}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<

6、=n;i++)sum+=p[i].x*p[i+1].y-p[i].y*p[i+1].x;returnsum/2.0;}constdoubleEPS=1e-9;constdoublemaxn=1e6-1;constdoublePI=acos(-1.);constintM=100+5;constdoubleoffset=11213;#definezero(x)(((x)>0?(x):-(x))

7、,b,c;};doubledist(Pointa,Pointb){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}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(LINESE

8、GL,Pointq){returnfabs(multiply(L.ed,q,L.st))