先说下题意，很简单，给n个点的坐标，求距离最近的一对点之间距离的一半。
第一行是一个数n表示有n个点，接下来n行是n个点的x坐标和y坐标。实数。
这个题目其实就是求最近点对的距离。《算法导论》上有详细讲解，王晓东的书上也有代码。主要思想就是分治。先把n个点按x坐标排序，然后求左边n/2个和右边n/2个的最近距离，最后合并。
合并要重点说一下，比较麻烦。
首先，假设点是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个点。具体证明过程可以参看算法导论。
利用这个结论我们就可以来继续优化比较的过程了。刚刚我们是用用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)，非常快！
源代码(1):
/*分治算法求最小点对*//*AC代码：828ms*/#include <iostream>#include <cmath>#include <algorithm>#define MAXN 100005//#define min(a,b) (a<b?a:b)//为什么用这个就超时！！！using namespace std;struct Point{double x,y;};struct Point point[MAXN],*px[MAXN],*py[MAXN];double get_dis(Point *p1,Point *p2){return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));}bool cmpx(Point *p1,Point *p2) {return p1->x<p2->x;}bool cmpy(Point *p1,Point *p2) {return p1->y<p2->y;}double min(double a,double b){return a<b?a:b;}//——-核心代码————//double closest(int s,int e){if(s+1==e)return get_dis(px[s],px[e]);if(s+2==e)return min(get_dis(px[s],px[s+1]),min(get_dis(px[s+1],px[e]),get_dis(px[s],px[e])));int mid=(s+e)>>1;double ans=min(closest(s,mid),closest(mid+1,e));//递归求解int i,j,cnt=0;for(i=s;i<=e;i++)//把x坐标在px[mid].x-ans~px[mid].x+ans范围内的点取出来{if(px[i]->x>=px[mid]->x-ans&&px[i]->x<=px[mid]->x+ans)py[cnt++]=px[i];}sort(py,py+cnt,cmpy);//按y坐标排序for(i=0;i<cnt;i++){for(j=i+1;j<cnt;j++)//py数组中的点是按照y坐标升序的{if(py[j]->y-py[i]->y>=ans)break;ans=min(ans,get_dis(py[i],py[j]));}}return ans;}int main(){int i,n;while(scanf("%d",&n)!=EOF){if(n==0)break;for(i=0;i<n;i++){scanf("%lf%lf",&point[i].x,&point[i].y);px[i]=&point[i];}sort(px,px+n,cmpx);//for(i=0;i<n;i++)// printf("(%.2lf,%.2lf)–",px[i].x,px[i].y);double distance=closest(0,n-1);printf("%.2lf\n",distance/2);}return 0;}
参考网上思路，由于这题数据比较弱，（是网上说的，不过确实很弱）。可以以一种投机取巧的枚举水过。。。
具体方法：对点进行x轴排序，这样，可以知道最短的距离最有可能出现的是在两个相邻的点之间（但不一定），所以我枚举了离当前点距离（只看x轴）最近的50个点，这样，最短距离一般就在里面了。但是更让人吃惊的是，这题数据弱到，只要对x轴排序，枚举相邻3个点就可以A掉。。。。囧。。。。。
%D1%EE%D7%D3%D1%DC/blog/item/4b4da1ece0365a4379f05571.html
源代码(2):
/*最近点对(枚举)*//*AC代码：609ms*/#include <iostream>#include <cmath>#define min(a,b) (a<b?a:b)#define MAXN 100005#define INF 99999999#define step 2struct point{double x,y;};struct point ps[MAXN];double ansr;int N;int cmp1(const void *p1,const void *p2){if(((struct point *)p1)->x!=((struct point *)p2)->x)return ((struct point *)p1)->x>((struct point *)p2)->x?1:-1;return ((struct point *)p1)->y>((struct point *)p2)->y?1:-1;}int cmp2(const void *p1,const void *p2){if(((struct point *)p1)->y!=((struct point *)p2)->y)return ((struct point *)p1)->y>((struct point *)p2)->y?1:-1;return ((struct point *)p1)->x>((struct point *)p2)->x?1:-1;}double get_dis(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}void work(){int i,j;for(i=1;i<=N;i++)for(j=i+1;j<=N&&j<=i+step;j++)ansr=min(ansr,get_dis(ps[i],ps[j]));}int main(){int i;while(scanf("%d",&N)!=EOF){if(N==0)break;for(i=1;i<=N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);ansr=INF;qsort(ps+1,N,sizeof(ps[0]),cmp1);work();//qsort(ps+1,N,sizeof(ps[0]),cmp2);//work();printf("%.2lf\n",ansr/2);}return 0;}
double min(double a,double b){return a<b?a:b;}就AC。
也有伤心的，既有令人兴奋的，也有令人灰心的，
