最近点对分治法

假设在一片金属上钻n个大小一样的洞，如果洞太近，金属可能会断。假设知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。如果不用分治法，问题非常容易解决。也就是蛮力法。代码如下：#include<stdio.h>#include<math.h>typedefstructTYPE{doublex,y;}Point;floatdist(Pointa,Pointb){return(float)sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}floatnearest(Point*points,intn){floattemp,near1=10000;inti,j;if(n==1){printf("不可能");return0;}else{for(i=0;i<n-1;i++)for(j=i+1;j<n;j++){{temp=dist(points[i],points[j]);near1=(near1>temp)?temp:near1;}} returnnear1;}}intmain(){intn,i;doubled;printf("输入点的个数：");scanf("%d",&n);Pointa[10000];while(n){for(i=0;i<n;i++)scanf("%lf%lf",&(a[i].x),&(a[i].y));d=nearest(a,n);printf("%.2lf\n",d);scanf("%d",&n);}return0;}但是此题是用分治法，我也参考了网上很多资料，他们要求对纵坐标进行排序，可能是为了对求右边的问题的点扫描用for循环，但我发现那算法就不对，但愿是我的还没有完全明白按纵坐标排序的原因，我参考的资料：代码如下：#include<stdio.h>#include<stdlib.h>#include<math.h>#defineMAX_POINTS100000/*坐标点数的最大值*/#defineMAX_TEST100/*最大测试次数*/typedefstruct{/*定义坐标点*/floatx;floaty;}Point;floatdist(Pointa,Pointb){/*求两个坐标点之间的距离*/returnsqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}floatNearest(Point*points,intn){/*求最小距Nearest的函数*/floattemp1,temp2,temp3,temp,nearest;floatleft,right,d;inti,j;if(n==1)printf("距离为0");/*一个点情形,返回值模拟0。也可以用retrun0来代替*/if(n==2)returndist(points[0],points[1]);/*两个点情形,调用dist函数*/if(n==3){/*三个点情形时，分别计算出距离，然后两两比拟*/temp1=dist(points[0],points[1]);temp2=dist(points[0],points[2]);temp3=dist(points[1],points[2]);returntemp3<((temp1<temp2)?temp1:temp2)?temp3:((temp1<temp2)?temp1:temp2);}/*多于3点的情形，用分治法*/left=Nearest(points,n/2);/*递归求解求左边点对的最小距离*/right=Nearest(&points[n/2],n-n/2);/*递归求解求右边点对的最小距离*/d=left<right?left:right;/*综合中间带求得最小距离*///将P1和P2中所有S的点按其x坐标排好序，那么对P1中所有点p，//对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，//对P1中每一点最多只要检查P2中排好序的相继6个点。nearest=d;for(i=0;i<n/2;i++)/*通过扫描子集一中每个点检查子集二中与其距离在d之内的所有点(最多6个)以完成合并*/ for(j=n/2;j<n&&(fabs(points[j].y-points[i].y)<d);j++){//跨场地的点对的y轴值的差的绝对值与d比拟temp=dist(points[i],points[j]);nearest=nearest<temp?nearest:temp;}returnnearest;}intcompx(constvoid*a,constvoid*b){//定义比拟函数，常量指针const指向的区域*a,*b不可修改，大于，返回>0;小于，返回<0;相等，返回0/*实现按x排序*/return((Point*)a)->x-((Point*)b)->x;}intcompy(constvoid*a,constvoid*b){/*实现按y排序*/return((Point*)a)->y-((Point*)b)->y;}voidmain(){inti,j=0,numPoints;Pointpoints[MAX_POINTS];//类point的数组,用来存放点对floatresult[MAX_TEST];/*定义一个每次测试结果的数组*/for(i=0;i<MAX_TEST;i++)result[i]=-1;//初始化测试结果，全部设置为-1printf("请输入数据：\n");while(1){/*进行屡次测试*/loop:printf("请输入你要在金属板上钻孔的个数："); scanf("%d",&numPoints);if(!numPoints)break;//如果输入点数0，跳出循环if(numPoints<0||numPoints>MAX_POINTS){printf("非法输入，请重新输入点的个数!\n");/*报错！*/gotoloop;} printf("请依次输入各圆孔中心点的x,y坐标：\n");for(i=0;i<numPoints;i++){/*输入点的数量及点的坐标值*/ printf("请输入第%d个圆孔中心点的x,y轴坐标：",i+1);scanf("%f%f",&points[i].x,&points[i].y); printf("\n"); }/*预先将S中的n个点依其x坐标排序好,方便画出中间线，使得场地点数大致相等。*/qsort(points,numPoints,sizeof(Point),compx);//compx为指针，是指向compx函数，用于确定排序的顺序//编译器函数库自带的快速排序函数qsort(points,numPoints/2,sizeof(Point),compy);//对y轴点对上半局部排序qsort(points+numPoints/2,numPoints-numPoints/2,sizeof(Point),compy);//对y轴点对下半局部排序result[j]=Nearest(points,numPoints);j++;//j加1，表示记录了该次结果后，再在数组result[]中记录下次的测试结果}i=0;//输入点数为0个时，就输出结果printf("两圆孔中心的最短距离为：\n");while(result[i]!=-1)/*不为-1时〔因为此时已经有了实际的结果，就输出屡次测试的结果*/printf("%.4f\n",result[i++]);}他的算法是有问题的：假设点是〔-5,2〕，〔-3，-2〕，〔-0.5，-100〕和点〔0,1〕得到的最近点对距离是4.47所以我就没有点的纵坐标进行排序，而且输出了，在分治法中找出并输出满足左边的点的时候，同时也输出满足右边的点。代码如下：#include<iostream>#include<cmath>usingnamespacestd;constintN=100005;constdoubleeps=0.00001;typedefstructTYPE/*定义坐标点*/{doublex,y;}Point;Pointa[N];doubleclosest(Point*,int);//求点队中最近点对的距离doubledis(Point,Point);//求二点间的距离intcmp_x(constvoid*,constvoid*);doublemin(double,double);//二者中的小者intmain(){intn,i;doubled,dist;printf("输入金属板能接受的最小距离：");scanf("%lf",&dist);printf("输入钻孔的点的个数：");//输入点的个数scanf("%d",&n); while(n)//用循环给n个点赋予横，纵坐标值{for(i=0;i<n;i++)scanf("%lf%lf",&(a[i].x),&(a[i].y));qsort(a,n,sizeof(a[0]),cmp_x);//编译器函数库自带的快速排序函数 //输出按横坐标排序后的点对 printf("输出按横坐标排序后的点\n"); for(i=0;i<n;i++)printf("%.2lf%.2lf\n",a[i].x,a[i].y);d=closest(a,n);//调用求点对中的最小距离printf("所有点对中最近点的距离:%.2lf\n",d);//输出最近点对的距离if(d<dist)printf("金属板可能会断掉。\n");elseprintf("金属板完好。\n");printf("输入点的个数：");scanf("%d",&n);}return0;}doubleclosest(Point*a,intn){doubled1,d2;doubletemp;if(n==2)//求出二个点的距离 { doubled=dis(a[0],a[1]);printf("调用二个点求距离值：%.2lf\n",d);returnd; }if(n==3)//求出三个点的距离{doublex1=dis(a[0],a[1]);doublex2=dis(a[1],a[2]);doublex3=dis(a[2],a[0]); printf("调用三个点求距离的最小值:");if(x1<x2&&x1<x3) { printf("%.2lf\n",x1);returnx1; }elseif(x2<x3) {printf("%.2lf\n",x2);returnx2; }else { printf("%.2lf\n",x3);returnx3; }}d1=closest(a,n/2);//左局部递归调用closest函数d2=closest(&a[n/2],n-n/2);//右局部递归调用closest函数doubledm=min(d1,d2);//求出左右局部中的最小者printf("左局部和右局部中的较小者:");//左局部和右局部中的较小者dmprintf("%.2lf\n",dm);doublenearest=dm;doublePI=100000;inti=0;while(i<n/2) { if(a[n/2].x-a[i].x<dm)//寻找左局部中距中间点的横坐标距离小于dm { printf("满足左局部\n"); printf("%.2lf%.2lf\n",a[i].x,a[i].y); int j=n/2; inth=0; while(j<n) {if(j<n&&(a[j].x-a[n/2].x)<dm&&fabs(a[j].y-a[i].y)<dm)//寻找此时距左局部的点纵坐标距离小于dm的右局部的点 { while(h==0) { h=1; printf("满足右局部\n"); } printf("%.2lf%.2lf",a[j].x,a[j].y);temp=dis(a[i],a[j]);