/** 最近点对问题，时间复杂度为O(n*logn*logn) */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double INF = 1e20; const int N = 100005; struct Point { double x; double y; }point[N]; int n; int tmpt[N]; bool cmpxy(const Point& a, const Point& b) //cmpxy这种写法只能和sort结合运用 { if(a.x != b.x) return a.x < b.x; return a.y < b.y; } bool cmpy(const int& a, const int& b) //cmpy这种写法只能和sort结合运用 { return point[a].y < point[b].y; } double min(double a, double b) { return a < b ? a : b; } double dis(int i, int j) { return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x) + (point[i].y-point[j].y)*(point[i].y-point[j].y)); } double Closest_Pair(int left, int right) { double d = INF; if(left==right) return d; if(left + 1 == right) return dis(left, right); //到最后会返回最小两点的距离-------1 int mid = (left+right)>>1; //这个骚操作的意思：>>是右移运算符，5>>1 的意思是将5表示为二进制后把末尾的数删去，其最终效果等同于5/2，是用来取降位平均数的 double d1 = Closest_Pair(left,mid); //上接第一步，返回值给了d1，d2，然后进行以下一系列操作--------2 double d2 = Closest_Pair(mid+1,right); d = min(d1,d2); int i,j,k=0; //分离出宽度为d的区间 for(i = left; i <= right; i++) { if(fabs(point[mid].x-point[i].x) <= d) //fabs 求浮点类型的绝对值，与abs有点相似 用 <d 虽然可能扩大复杂度，但是只有如此了 tmpt[k++] = i; } sort(tmpt,tmpt+k,cmpy); //线性扫描 for(i = 0; i < k; i++) { for(j = i+1; j < k && point[tmpt[j]].y-point[tmpt[i]].y<d; j++) //在此步骤做真正的判断，所以虽然前面可能扩大了各种可能性，但到此处都会解决的 { double d3 = dis(tmpt[i],tmpt[j]); if(d > d3) d = d3; } } return d; //上接第二步，在完成操作以后继续返回给上一级调用的函数，也就是返回第二步---------3 } //从倒推来看整个函数的运行过程为1-2-3-2-3-2-3...... int main() { while(true) { scanf("%d",&n); if(n==0) break; for(int i = 0; i < n; i++) scanf("%lf %lf",&point[i].x,&point[i].y); sort(point,point+n,cmpxy); printf("%.2lf ",Closest_Pair(0,n-1)/2); //此处left和right均为下标，2是除在外面的。。。看错了 } return 0; }
借鉴了大神的经验，并对c++不懂得语法进行了注释。
加一条，结构体名字和定义的结构体类的名字不能相同。
http://blog.csdn.net/lonelycatcher/article/details/7973046