最近点对分治法.doc

假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。 如果不用分治法 ，问题非常容易解决。也就是蛮力法。 代码如下： #include stdio.h #include math.h typedef struct TYPE { double x, y; } Point; float dist(Point a,Point b) { return (float)sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } float nearest(Point* points, int n) { float temp,near1=10000; int i,j; if(n==1) { printf(不可能); return 0; } else{ for(i=0; in-1; i++) for(j=i+1; jn; j++){ { temp=dist(points[i],points[j]); near1=(near1temp)?temp:near1; } } return near1; } } int main() { int n, i; double d; printf(输入点的个数：); scanf(%d, n); Point a[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); } return 0; } 但是本题是用分治法，我也参考了网上很多资料，他们要求对纵坐标进行排序，可能是为了对求右边的问题的点扫描用for循环，但我发现那算法就不对，但愿是我的还没有完全明白按纵坐标排序的原因， 我参考的资料：/p-198711591.html?qq-pf-to=pcqq.c2c 代码如下： #include stdio.h #include stdlib.h #include math.h #define MAX_POINTS 100000 /*坐标点数的最大值 */ #define MAX_TEST 100 /*最大测试次数*/ typedef struct { /*定义坐标点*/ float x; float y; }Point; float dist(Point a, Point b) { /*求两个坐标点之间的距离*/ return sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } float Nearest(Point* points, int n){ /*求最小距Nearest的函数*/ float temp1,temp2,temp3,temp,nearest; float left,right,d; int i,j; if(n==1) printf(距离为0); /*一个点情形,返回值模拟0。也可以用retrun 0来代替*/ if(n==2) return dist(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]); return temp3((temp1te