问题描述

n个点在公共空间中，求出所有点对的欧几里得距离最小的点对。

 

解法1： 很明显的，暴力解决是$O(N^2)$

 

解法2： 利用分治的思想，我们可以把算法优化到$O(nlogn*logn)$，甚至$O(nlogn)$

我们先对所有的点按照x坐标排序， 然后每次二分，很明显，这个二分很好写，难的是合并的操作。  即从左边A集合中选出一个点和右边集合B里面选出一个点。 

如果暴力的是去枚举左边和右边的点，还是$O(n^2)$。 

首先，我们先求出左边和右边集合的最小距离。 $d=min(dist_{left},dist_{right})$ 

 然后找出一个条左右集合的分界线。 如图所示

l就是左右集合的分界线。 

我们发现，我们只要在左边集合里面枚举横坐标在[mid-d,mid]和右边集合里面横坐标在[mid,mid+d]范围内的点进行配对就可以了。 因为明显的，另外的点的距离肯定更大。  

这样就大大缩小了我们枚举的范围，但是极端情况还是很大。 

 

 

1985年Preparata和Shamos在给出该问题的一个分治算法，指出对于左边的任意一个点，右边集合和他可以匹配成为最有解的最多只有6个点。

如图所示： 假如左边是p点，那么在分界线的右边和p点可以配对的点不会超过6个，即在那个δ×2δ的区间里面最多只有6个点。  

 

我们用反证法来证明。  

我们把δ×2δ这个矩阵按每$ \frac{2δ}{3}$来分，这样就有6个小矩形了我们可以知道每个小矩阵里面最多只有一个点，如果有两点，那么这两个点的距离一定要远一点，明显的，对角线的距离最短。 

此时对角线的距离就是$\sqrt{\frac{2δ}{3}×\frac{2δ}{3}+\frac{δ}{2}×\frac{δ}{2}}=\frac{\sqrt{5}}{6}δ$

此时说明右边原来就是小于d的点对（d和δ这里是一样的） ，明显与原来不符。 

所以最多只有6个点。（当然了，其实还能证明更少点）  

所以我们每次合并，对于左边的点最多只有6个匹配的方案。 考虑匹配方案的时候，需要对y进行排序，那么时间复杂度就变成了$O(n*logn*logn)$。  

但是其实我们可以做的更好，我们可以在分治的过程中，顺便做一个关于y坐标的归并排序，这样就不用每次对y进行sort了，时间也可以优化到$O(nlogn)$

下面是我的代码，还是写了2个$logn$的做法。 

1 #include
      
        2 using namespace std;  3 int const N=100000+10;    4 struct node{ 5     double x,y;   6 }a[N];   7 int cmpx(int t1,int t2){ 8     return a[t1].x
       
        a[t2].y;  12 }13 int n,t[N],c1[N],cnt1,c2[N],cnt2;    14 double dist(int t1,int t2){15     return sqrt( (a[t1].x-a[t2].x)*(a[t1].x-a[t2].x)+(a[t1].y-a[t2].y)*(a[t1].y-a[t2].y)); 16 }17 double calc(int l,int r,int mid,double d){18     sort(c1+1,c1+cnt1+1,cmpy);  19     sort(c2+1,c2+cnt2+1,cmpy);  20     int k=1;    21     double ret=d;  22     for(int i=1;i<=cnt1;i++) {23         while (k<=cnt2 && a[c2[k]].y-a[c1[i]].y>d) k++; 24         for(int j=k;j<=cnt2;j++)   25             if( a[c1[i]].y-a[c2[j]].y
        
         =0) c1[++cnt1]=t[i];  43     }      44     for(int i=mid+1;i<=r;i++){45         int dd=a[t[i]].x-a[t[mid]].x;  46         if(dd
         
          =0) c2[++cnt2]=t[i];  47     }  48     49     return calc(l,r,mid,d);50 }     51 int main(){52     while (scanf("%d",&n)!=EOF){53         if(n==0) break;  54         for(int i=1;i<=n;i++)  55             scanf("%lf%lf",&a[i].x,&a[i].y);  56         for(int i=1;i<=n;i++) t[i]=i;  57         sort(t+1,t+n+1,cmpx);  58         printf("%0.2lf\n",close_dist(1,n)/2);  59     }60     return 0; 61 }