问题描述
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<bits/stdc++.h> 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].x; 9 } 10 int cmpy(int t1,int t2){ 11 return a[t1].y>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<d) 26 ret=min(ret,dist(c1[i],c2[j])); 27 else break; 28 } 29 return ret; 30 } 31 32 double close_dist(int l,int r){ 33 if(l==r) return 1e9; 34 if(l+1==r) return dist(t[l],t[r]); 35 int mid=(l+r)/2; 36 double d1=close_dist(l,mid); 37 double d2=close_dist(mid+1,r); 38 double d=min(d1,d2); 39 cnt1=cnt2=0; 40 for(int i=l;i<=mid;i++){ 41 double dd=a[t[mid]].x-a[t[i]].x; 42 if(dd<d && dd>=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<d && 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 }