题目描述
给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的
输入格式
第一行：n ，保证 2≤n≤200000 。
接下来 n 行：每行两个实数：x y ，表示一个点的行坐标和列坐标，中间用一个空格隔开。
输出格式
仅一行，一个实数，表示最短距离，精确到小数点后面 4 位。
输入输出样例
输入 #1
3 1 1 1 2 2 2
输出 #1
1.0000
说明/提示
数据保证 0≤x,y≤109
题意： 显而易见，这道题需要我们求平面上最近点距离。
分析： 大部分人看到这个问题应该都能想到暴力，不过这样的复杂度是O(n^2)的，显然不能切掉2e5的数据。其实这是一个经典分治问题，首先将各点按照x坐标升序排序。
将点集平均划分为两部分，一部分记作点集L，另一部分记作点集R。
这时要求的最短距离其实是L中点的最短距离、R中点的最短距离、L和R之间点的最短距离这三部分取最小值。前两部分可以递归求解，最重要的是第三部分的求解，只要求出第三部分那问题就解决了。
设L中点最近距离为dl（图中p2到p5），R中点最近距离为dr（图中p7到p9），二者取最小值为d，L和R之间点的最短距离要想更新答案就需要比d还要小，因此只需要求两点集间可能会小于d的距离，哪些点既位于不同点集距离又可能小于d呢？这些点就是到分界线p[mid].x的距离小于d的所有点构成的集合，也就是下图中的候选点集。显然，这个点集外面的点与对侧点之间的距离一定大于等于d，不可能使d变得更小，因此也就不用考虑这些点。
之后可以遍历候选点集中的点，依次两两求距离判断是否可以更新d，但这样复杂度还是略高，其实还可以进一步优化。将点集中的点按y坐标升序排列，然后再遍历点，这样可以多一个剪枝条件，例如第一层循环遍历点是p4，然后再第二层循环依次遍历点p2、p5、p6、p3，其中到p6就可以退出循环了，因为p6的y坐标和p4的y坐标差值大于d，它们的距离也一定大于d，后面的p3更不用判断了，它的y值比p6还要大。
可以发现上面的过程进行了一些多余的比较，比如p2和p3之间的距离其实没必要计算，因为它们并不分属于L点集和R点集，不过在求最值问题中是允许的，只要能覆盖待求的情况就行。
时间复杂度是O(n*logn*logn)，分析过程见P1429 平面最近点对中syksykCCC大佬的题解。
具体代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#define pdd pair<double, double>
#define x first
#define y second
using namespace std;
const int maxn = 400005;
pdd p[maxn];
inline double dis(pdd a, pdd b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
bool cmpx(pdd a, pdd b)
{
return a.x < b.x;
}
bool cmpy(int a, int b)
{
return p[a].y < p[b].y;
}
double solve(int l, int r)//点下标在l~r之间的最近点距离
{
if(r-l+1 == 2)
return dis(p[l], p[r]);
if(r-l+1 == 3)
return min(min(dis(p[l], p[l+1]), dis(p[l+1], p[l+2])), dis(p[l], p[l+2]));
int m = l+r>>1;
double dl = solve(l, m);
double dr = solve(m+1, r);
double d = min(dl, dr);
vector<int> temp;//保存一些可能更新最短距离的点
for(int i = l; i <= r; i++)
if(fabs(p[i].x-p[m].x) < d)
temp.push_back(i);
sort(temp.begin(), temp.end(), cmpy);
//逐个检查是否可以更新
for(int i = 0; i < temp.size(); i++)
for(int j = i+1; j < temp.size() && p[temp[j]].y-p[temp[i]].y < d; j++)
d = min(dis(p[temp[i]], p[temp[j]]), d);
return d;
}
signed main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p+1, p+1+n, cmpx);
double ans = solve(1, n);
printf("%.4f\n", ans);
return 0;
}