分治法--凸包

//纯代码#includestdio.h#definePPmax30typedefstructnode{floatx,y;}Point;PointDingDian[PPmax];//用于存放凸边形的顶点intDingDnum=0;typedefstructPointss{Pointp1,p2;}SDian;SDianBDD[PPmax];//存放凸边形边的双点intBDDnum=0;//记录已经存入的双点数intabc=0;//全局变量，用来记录划边顺序voiddianxu(PointP[],intn)//对已经输入的点数组进行排序{//存放点的数组P[],点的个数n//——点排序//具体实现：(选择排序实现)//1.按x坐标从小到大排//2.扫描最前端点元素//2.1若不存在相同x坐标的点，则执行3//2.2若存在相同x坐标的点，按|y|排列大-小//3.扫描最后端点元素//3.1若不存在相同x坐标的点，则执行4//3.2若存在相同x坐标的点，按|y|排列小-大//4.返回。Pointtemp;inti,j;intmin,max;floatpx;intpxnum;//按x坐标排序for(i=0;i=n-2;i++){min=i;for(j=i+1;j=n-1;j++){if(P[j].xP[min].x){min=j;}}temp=P[i];P[i]=P[min];P[min]=temp;}//数组两端相同x按|y|排序//前端排序px=P[0].x;pxnum=1;while(P[pxnum].x==px){pxnum++;}for(i=0;i=pxnum-2;i++){//max=i;min=i;for(j=i+1;j=pxnum-1;j++){if(P[j].yP[min].y){min=j;}}temp=P[i];P[i]=P[min];P[min]=temp;}//后端排序px=P[n-1].x;pxnum=1;while(P[n-1-pxnum].x==px){pxnum++;}for(i=n-pxnum;i=n-2;i++){min=i;for(j=i+1;j=n-1;j++){if(P[j].yP[min].y){min=j;}}temp=P[i];P[i]=P[min];P[min]=temp;}return;}voidKuaibao(PointP[],intl,intr){//P[]:存放点的数组，l,r数组中点起始与终止坐标//Rtmin,Ltmax用来存放最大最小的t值floatt,Ltmax=0;PointPmax;intLnum=0;intLL;inti,imax;//连接p[l],p[r]暂时用下面方式实现printf(%2d(%.2f,%.2f)--(%.2f,%.2f),++abc,P[l].x,P[l].y,P[r].x,P[r].y);i=(lr)?l:r;imax=(lr)?l:r;for(i=i+1;iimax;i++){t=P[l].x*P[r].y+P[i].x*P[l].y+P[r].x*P[i].y-P[i].x*P[r].y-P[r].x*P[l].y-P[l].x*P[i].y;//判断t正负，t0，Lnum++；（Lnum初值为0）//if(tLtmax)Ltmax=t;Pmax=p[i];if(tLtmax){Lnum++;LL=i;Ltmax=t;Pmax=P[i];}}if(Lnum0){printf(\n);DingDian[DingDnum++]=P[LL];//将P[LL]放入顶点集Kuaibao(P,l,LL);Kuaibao(P,LL,r);}else//t=0时，将P[l]、P[r]放入边集{printf(\r边--\n);BDD[BDDnum].p1=P[l];//存放凸边形边的双点BDD[BDDnum].p2=P[r];BDDnum++;//记录已经存入的双点数return;}}intmain(){intn;inti;intl,r;PointP[PPmax];printf(输入点的个数：);scanf(%d,&n);for(i=0;in;i++){scanf(%f%f,&P[i].x,&P[i].y);}dianxu(P,n);printf(点序：\n);for(i=0;in;i++){printf((%.2f%.2f)\n,P[i].x,P[i].y);}l=0;r=n-1;//将p[l],p[r]存入顶点集DingDian[]DingDian[DingDnum++]=P[l];DingDian[DingDnum++]=P[r];printf(画边顺序：\n);Kuaibao(P,l,r);Kuaibao(P,r,l);printf(\n所有边如下：\n);for(i=0;iBDDnum;i++)//BDDnum记录已经存入的双点数{//BDD[BDDnum]存放凸边形边的双点printf((%.2f,%.2f)--(%.2f,%.2f)\n,BDD[i].p1.x,BDD[i].p1.y,BDD[i].p2.x,BDD[i].p2.y);}printf(\n);printf(\n所有顶点如下：\n);for(i=0;iDingDnum;i++){printf((%.2f,%.2f)\n,DingDian[i].x,DingDian[i].y);}return0;}