给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

考虑以下分治算法：

设平面上的点都在点集S中，为了将S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l（方程：x=m）来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2 。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离δ1和δ2。现设δ=min (δ1,δ2)。

若S的最接近点对(p,q)之间的距离d(p,q)<δ则p和q必分属于S1和S2。不妨设p∈S1，q∈S2。那么p和q距直线l的距离均小于δ。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈S1，q∈S2

此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n^2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)<δ。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个δ×2δ的矩形R中，

由δ的意义可知P2中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上，我们可以将矩形R的长为2δ的边3等分，将它的长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形。

因此d(u,v)≤5δ/6<δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n^2/4对候选者。

我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点，但是我们并不确切地知道要检查哪6个点。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于δ。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。

至此，我们用分治法求出平面最接近点对。
时间复杂度：O(nlogn)

#include<bits/stdc++.h> // https://www.luogu.com.cn/problem/P1429

using namespace std;

const int maxn = 1e6 + 1;

struct point{
    double x, y;
    point(){}
    point(double x, double y): x(x), y(y) {}
    point operator- (const point &n1) {return point(x-n1.x, y-n1.y);}
    bool operator< (const point &n1) {return x < n1.x;}
}p[maxn], temp[maxn];

double dot(point a, point b) {return a.x*b.x + a.y*b.y;}

double MinDis(int l, int r) { // 最近点对
    if (r - l <= 1) { // 点数为1或2
        if (l == r) return INT_MAX;
        if (p[l].y > p[r].y) swap(p[l], p[r]);
        return sqrt(dot(p[l]-p[r], p[l]-p[r]));
    }
    int mid = l+r >> 1;
    double dis = min(MinDis(l, mid), MinDis(mid+1, r));
    // 归并排序
    int t1 = l, t2 = mid + 1, tot = 0;
    while(t1 <= mid && t2 <= r) {
        if (p[t1].y < p[t2].y) temp[++tot] = p[t1++];
        else                   temp[++tot] = p[t2++];
    }
    while(t1 <= mid) temp[++tot] = p[t1++];
    while(t2 <= r)   temp[++tot] = p[t2++];
    for(int i = l; i <= r; ++ i) {
        p[i] = temp[i - l + 1];
    }
    // 更新中间区域最近点对
    for(int i = l, tot = 0; i <= r; ++ i) {
        if (p[i].x > p[mid].x - dis && p[i].x < p[mid].x + dis) {
            temp[++tot] = p[i];
        }
    }
    for(int i = 1; i <= tot; ++ i) {
        for(int j = i + 1; j <= tot && j <= i + 6; ++ j) {
            dis = min(dis, sqrt(dot(p[j]-p[i], p[j]-p[i])));
        }
    }
    return dis;
}


int main() {
    int n; while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++ i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        printf("%.4f\n", MinDis(1, n));
    }
    return 0;
}