首先，假设点是n个，编号为1到n。我们要分治求，则找一个中间的编号m，先求出1到m点的最近距离设为d1，还有m+1到n的最近距离设为d2。这里的点需要按x坐标的顺序排好，并且假设这些点中，没有2点在同一个位置。（若有，则直接最小距离为0了）。
然后，令d为d1, d2中较小的那个点。如果说最近点对中的两点都在1-m集合中，或者m+1到n集合中，则d就是最小距离了。但是还有可能的是最近点对中的两点分属这两个集合，所以我们必须先检测一下这种情况是否会存在，若存在，则把这个最近点对的距离记录下来，去更新d。这样我们就可以得道最小的距离d了。
关键是要去检测最近点对，理论上每个点都要和对面集合的点匹配一次，那效率还是不能满足我们的要求。所以这里要优化。怎么优化呢？考虑一下，假如以我们所选的分割点m为界，如果某一点的横坐标到点m的横坐标的绝对值超过d1并且超过d2，那么这个点到m点的距离必然超过d1和d2中的小者，所以这个点到对方集合的任意点的距离必然不是所有点中最小的。
所以我们先把在m为界左右一个范围内的点全部筛选出来，放到一个集合里。
筛选好以后，当然可以把这些点两两求距离去更新d了，不过这样还是很慢，万一满足条件的点很多呢。这里还得继续优化。首先把这些点按y坐标排序。假设排序好以后有p个点，编号为1到p。那么我们用1号去和2到p号的点求一下距离，然后2号和3到p号的点求一下距离。。。还没完，因为这样比，求的次数还是O(p^2), 所以其实和没优化没区别。
假设有一个点q,坐标是xq, yq。可以证明在以q为底边中点，长为2d，宽为d的矩形区域内不会有超过6个点。具体证明过程可以参看算法导论。///GGGGG
利用这个结论我们就可以来继续优化比较的过程了。刚刚我们是用用1号点去和2到p号的点求一下距离，我们知道以1号点构造图中矩形内，不会有超过6个点存在。但是我们又不能直接从1号求到6号，因为这里的p个点是按y坐标排序而不是按距离排序的，有可能在y坐标上，前10个点距离1号点都很近，但是前6个点的x坐标很远，而第10个点的x坐标和1号点的x坐标很进，这样第10个点到1号点的距离反而更近。
那么我们怎么利用这个结论呢？应该这样，假设1号点和2到p号点比较，由于y坐标排序的缘故，假设第p个点的y坐标距离1号点的y坐标大于当前能求出的最小值，那么这点以及这点后的所有点距离1号点的距离必然大于当前已经获得的最小值，所以直接不用比较后面的了。
又因为满足比较条件的点很少，不会超过6个，所以这里可以看成O(1)的效率。那么整个算法的效率大概是在O(nlogn)，非常快！
都是抄别人的 就拿个版
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<queue> #include<set> using namespace std; #define ll long long #define inf 1000000007 #define MAXN 100010 #define exp 1e-4 struct point { double x,y; }px[MAXN],py[MAXN]; double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool cmpx(point a,point b) { return a.x<b.x; } bool cmpy(point a,point b) { return a.y<b.y; } double closet(int l,int r) { if(l+1==r) return dis(px[l],px[r]); if(l+2==r) return min(min(dis(px[l],px[l+1]),dis(px[l],px[r])),dis(px[l+1],px[r])); int mid=(l+r)>>1; double ans=min(closet(l,mid),closet(mid+1,r)); int cnt=0; for(int i=l;i<=r;i++) { if(px[i].x>=px[mid].x-ans&&px[i].x<=px[mid].x+ans) py[cnt++]=px[i]; } sort(py,py+cnt,cmpy); for(int i=0;i<cnt;i++) { for(int j=i+1;j<cnt;j++) { if(py[j].y-py[i].y>=ans) break; ans=min(ans,dis(py[i],py[j])); } } return ans; } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=0;i<n;i++) scanf("%lf%lf",&px[i].x,&px[i].y); sort(px,px+n,cmpx); double ans=closet(0,n-1); printf("%.2lf ",ans/2); } return 0; }