算法：
0：把所有的点按照横坐标排序
1：用一条竖直的线L将所有的点分成两等份
2：递归算出左半部分的最近两点距离d1，右半部分的最近两点距离d2，取d=min(d1,d2)
3：算出“一个在左半部分，另一个在右半部分”这样的点对的最短距离d3。
4：结果＝min(d1,d2,d3)
关键就是这第3步。貌似这需要n^2的时间，把左边每个点和右边每个点都对比一下。其实不然。秘密就在这里。
首先，两边的点，与分割线L的距离超过d的，都可以扔掉了。
其次，即使两个点P1,P2（不妨令P1在左边，P2在右边）与分割线L的距离（水平距离）都小于d，如果它们的纵坐标之差大于d，也没戏。
就是这两点使得搜索范围大大减小：
对于左半部分的，与L的距离在d之内的，每个P1来说：右半部分内，符合以上两个条件的点P2最多只有4个！
原因就是：
d是两个半平面各自内，任意两点的最小距离，因此在同一个半平面内，任何两点距离都不可能超过d。
我们又要求P1和P2的水平距离不能超过d，垂直距离也不能超过d，在这个d*2d的小方块内，最多只能放下8个距离不小于d的点。
因此，第3步总的比较距离的次数不超过n*8。
第3步的具体做法是：
3.1 删除所有到L的距离大于d的点。 O(n)
3.2 把右半平面的点按照纵坐标y排序。 O(nlogn)
3.3 对于左半平面内的每个点P1,右半平面内的与P1构成点对的距离小于d的点P2一定在P1后面跟随的8个位置上（已按坐标y排序），算出d3。 O(n*8) = O(n)
因为3.2的排序需要O(nlogn)，
所以整个算法的复杂度就是O(n((logn)^2))。
改进：
我们对3.2这个排序的O(nlogn)不太满意。
既然整个算法是递归的，我们可以利用第2步的子递归中已经排好序的序列，在第3.2部归并这两个子列，这样3.2的复杂度变成了O(n)。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max 100001
#define inf 0x3f3f3f3f
struct point
{
double x;
double y;
}a[Max];
int totalpoint;
double min_d;
struct point men_p1,men_p2;
double dist(struct point a,struct point b)
{
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
int cmx(const void *a,const void *b)
{
return (((struct point *)a)->x>((struct point *)b)->x)?1:-1;
}
int cmy(const void *a,const void *b)
{
return (((struct point *)a)->y>((struct point *)b)->y)?1:-1;
}
void rec_cl_pair(int i,int j)
{
struct point v[100];
double temp;
double middle;
int t,k,l;
if(j-i<=3)
{
qsort(a+i,j-i+1,sizeof(a[0]),cmy);
temp=dist(a[i],a[i+1]);
if(temp<min_d)
{
men_p1=a[i];
men_p2=a[i+1];
min_d=temp;
}
if(j-i==1)
{
return ;
}
temp=dist(a[i],a[i+2]);
if(temp<min_d)
{
men_p1=a[i];
men_p2=a[i+2];
min_d=temp;
}
temp=dist(a[i+1],a[i+2]);
if(temp<min_d)
{
men_p1=a[i+1];
men_p2=a[i+2];
min_d=temp;
}
return ;
}
k=(i+j)/2;
middle=a[k].x;
rec_cl_pair(i,k);
rec_cl_pair(k+1,j);
t=1;
for(k=i;k<=j;k++)
if(a[k].x>middle-min_d&&a[k].x<middle+min_d)
v[t++]=a[k];
qsort(v+1,t-1,sizeof(v[1]),cmy);
for(k=1;k<=t-1;k++)
{
for(l=k+1;l<(t-1<k+7?t-1:k+7);l++)
{
temp=dist(v[k],v[l]);
if(temp<min_d)
{
men_p1=v[k];
men_p2=v[l];
min_d=temp;
}
}
}
}
void close_pair()
{
int n=totalpoint;
qsort(a+1,n,sizeof(a[1]),cmx);
rec_cl_pair(1,n);
}
int main()
{
int i;
while(scanf("%d",&totalpoint)!=-1&&totalpoint)
{
for(i=1;i<=totalpoint;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
min_d=inf;
close_pair();
printf("%.2lf\n",min_d/2);
printf("(%.2lf,%.2lf) (%.2lf %.2lf)
\n",men_p1.x,men_p1.y,men_p2.x,men_p2.y);
}
return 0;
}
对于解决HDU 1007 Quoit Design
AC不过，超时（这个算法的O（nlg(n)居然也超时了）
下面附上已经AC的代码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max 100001
#define inf 0x3f3f3f3f
struct point
{
double x;
double y;
}a[Max];
int n;
int cmp(const void *a,const void *b)
{
struct point *p1=(point *)a;
struct point *p2=(point *)b;
if(p1->x==p2->x)
return p1->y>p2->y?1:-1;
return p1->x>p2->x?1:-1;
}
double dist(struct point a,struct point b)
{
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
double close_pair(int i)
{
double di,d=inf;
int j;
for(j=i+1;j<n;j++)
{
di=dist(a[i],a[j]);
if(di<d)d=di;
else break;/*关键在此*/
}
return d;
}
int main()
{
double f,ans;
int i;
while(scanf("%d",&n)!=-1&&n)
{
for(i=0;i<n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
qsort(a,n-1,sizeof(a[0]),cmp);
ans=inf;
for(i=0;i<n;i++)
{
f=close_pair(i);
if(f<ans)
ans=f;
}
printf("%.2lf\n",ans/2);
}
return 0;
}