分治法解决最小套圈问题.doc

附录:源代码
/* 分治法解决最小套圈问题*/
#include <>
#include <>
#include <>
#define MAX_POINTS 100000 /*坐标点数的最大值*/
#define MAX_TEST 100 /*最大测试次数*/
typedef struct { /*定义坐标点*/
float x;
float y;
}Point;
float dist(Point a, Point b) { /*求两个坐标点之间的距离*/
return sqrt((float)(-)*(-)+(-)*(-));
}
float Nearest(Point* points, int n){ /*求最小距离*/
float temp1,temp2,temp3,temp,nearest;
float left,right,d; /*当n小于4时,T(n)=O(1);*/
int i,j;
if(n==1) return 999999999; /*一个点情形,返回值模拟无穷*/
if(n==2) return dist(points[0], points[1]); /*两个点情形*/
if(n==3){ /*三个点情形*/
temp1=dist(points[0], points[1]);
temp2=dist(points[0], points[2]);
temp3=dist(points[1], points[2]);
return temp3<((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的点按其y坐标排好序,则对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++){
temp=dist(points[i],points[j]);
nearest=nearest<temp?nearest:temp;
}
return nearest;
}
px(const void* a, const void* b) {
/*实现按x排序*/
return ((Point*)a)->x-((Point*)b)->x;
}
py(const void* a, const void* b) {
/*实现按