题目描述

有n个坐标点，问这些点之间最近的一对点的距离是多少？

输入数据

多组输入(<=10组数据，读入以EOF结尾)。 每组第一行输入一个数字，n(1<=n<=) 表示坐标点的个数。 随后n行，为两个整数，表示对应的坐标点。

输出数据

每组输出一行结果，保留两位有效数字

样例输入

2 0 0 1 1 

讯享网

样例输出

讯享网1.41

解析：

1、为了使问题易于理解和分析，先来考虑一维的情形。此时，S中 的n个点退化为x轴上的n个实数 x1 , x2 , …, xn。最接近点对即为这 n个实数中相差最小的2个实数。

讯享网

 假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想， 用S中各点坐标的中位数来作分割点。

 递归地在S1和S2上找出其最接近点对{p1, p2}和{q1, q2}，并设d = min{|p1-p2|, |q1-q2|}，S中的最接近点对是{p1, p2}或者是{q1, q2}，或者是某个{p3, q3}，其 中p3∈S1且q3∈S2

2、对于二维情形：

选取一垂直线l: x = m来作为分割直线，其中m为S中各点x坐标的中位数。将S分割 为S1和S2。

递归地在S1和S2上找出其最小距离d1和d2，并设d = min{d1, d2}，S中的最接近 点对是d，或者是某个{p, q}，其中p∈S1且q∈S2。

3、对 p 和 q 的枚举

①候选点 p 和 q 到直线l 的距离不能超过d，则只需考虑区间P1和P2的范围；

②考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2 中的点一定落在一个d×2d的矩形R中；

③由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。

证明：将矩形R的长为2d的边3等分，将它的长为d的边2 等分，由此导出6个(d/2)×(2d/3)的矩形。若矩形R中有多 于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3) 的小矩形中有2个以上S中的点。设u，v是位于同一小矩形 中的2个点，则

distance(u,v)<d，这与 d 的意义相矛盾。

 

完整代码：

//求平面中点之间的最短距离 #include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; struct point { double x; double y; }; bool sortBy_x(point& point1, point& point2) //根据x坐标从小到大排序 { if (point1.x == point2.x) return point1.y < point2.y; return point1.x < point2.x; } double getDistance(point& point1, point& point2) //计算两点之间的距离 { double dis_x = point1.x - point2.x; double dis_y = point1.y - point2.y; return sqrt(dis_x*dis_x+dis_y*dis_y); } double getMin(vector<point>& vec, int low, int high) { if (high - low == 1) //2个结点 { return getDistance(vec[low], vec[low + 1]); } else if (high - low == 2) //3个结点 { double dist1= getDistance(vec[low], vec[low + 1]); double dist2 = getDistance(vec[low], vec[low + 2]); double dist3 = getDistance(vec[low+1], vec[low + 2]); return min(min(dist1, dist2), dist3); } else { int mid = (low + high) / 2; //cout<<"mid:"<<mid<<endl; double left_min = getMin(vec, low, mid); double right_min = getMin(vec, mid + 1, high); double d = min(left_min, right_min); //cout<<"left:"<<left_min<<" right:"<<right_min<<" d:"<<d<<endl; vector<point> res; int i, j,k=0; for (i = mid+1; i <= high; i++)//遍历另一侧，得到与横坐标与 中点横坐标距离在d以内的点 { if (fabs(vec[i].x - vec[mid].x) < d){ res.push_back(vec[i]); cout<<i<<endl; } } for (i = 0; i < res.size() - 1; i++) { if (fabs(vec[mid].y - res[i].y) >= d) //纵坐标距离超过 d break; double dp = getDistance(vec[mid], res[i]); if (dp < d) d = dp; } return d; } } int main() { int i, j, n; cin >> n; //输入点的个数 vector<point> vec; for (i = 0; i < n; i++) { point point1; cin >> point1.x >> point1.y; vec.push_back(point1); } sort(vec.begin(), vec.end(), sortBy_x);//先按照横坐标排序 cout << getMin(vec, 0, vec.size() - 1) << endl; return 0; } 

参考资料：https://blog.csdn.net/hnu2012/article/details/