编程之美2.11——寻找最近点对（POJ 3714）

问题：

给定平面上N个点的坐标，找出距离最近的两个点。

解法：

我们先对N个点的x坐标进行排序，排序我们使用最坏复杂度O(n*logn)的快速排序方法，在排序的过程中minDifferent会递归计算出左右两边的最小距离，再用其中的较小值minum得到以中位数点附近的带状区域[p[median+1].x-median, p[median].x+median]，对带状区域的点按照y坐标排序，对带状区域的每个点只需计算最多7个点，就能得到所有可能小于minum的点对。

#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;const double INF = 1e100;struct Point{double x, y;int flag;// 顶点的类别Point(){}Point(double xx, double yy):x(xx),y(yy){}};vector<Point> p;bool cmp1(const Point& a, const Point& b){return a.x < b.x;}bool cmp2(int a, int b){return p[a].y < p[b].y;}double dist(const Point& a, const Point& b){double xx = a.x - b.x;double yy = a.y - b.y;return sqrt(xx*xx+yy*yy);}// 输出属于不同类的顶点对的最小值double min_dist(vector<Point> p, int left, int right){int mid = (left+right)>>1, i,j;if (left>=right) return INF;for (i=mid; i>=left && p[mid].x<=p[i].x; i--);double minum = min_dist(p, left, i);for (i=mid; i<=right && p[i].x<=p[mid].x; i++);minum = min(minum, min_dist(p, i, right));vector<int> yp;for (i=mid; i>=left && p[mid].x-p[i].x<minum; i--)yp.push_back(i);for (i=mid+1; i<=right && p[i].x-p[mid].x<minum; i++)yp.push_back(i);// 这个方法非常巧妙，直接对顶点索引进行排序，减少了空间使用，// 代码上也更加简洁sort(yp.begin(), yp.end(), cmp2);for (i=0; i<yp.size(); i++)for (j=i+1; j<yp.size() && p[yp[j]].y-p[yp[i]].y<minum; j++)// 主要的不同之处，产生最小距离的点对必须属于不同类别if (p[yp[j]].flag != p[yp[i]].flag)minum = min(minum, dist(p[yp[j]], p[yp[i]]));return minum;}int main(){int i,j,test;cin >> test;while (test--){int xx,yy,n;cin >> n;for (i=0; i<n; i++){cin >> xx >> yy;p.push_back(Point(xx,yy));p[i].flag = 1;}for (; i<2*n; i++){cin >> xx >> yy;p.push_back(Point(xx,yy));p[i].flag = 2;}// 按照x坐标对点集进行排序sort(p.begin(), p.end(), cmp1);printf("%.3lf\n", min_dist(p, 0, p.size()-1));}}