题意

题目链接。

给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$，请输出距离最近的两个点的距离。

解析

在这题下给一篇正经的分治做法，已有的分治做法是用 vector 实现的，可能对于部分同学来说代码实现不便。其他题解都是非分治的。

我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$，记 $\operatorname{solve}(l,r)$ 为计算出 $[l,r]$ 内所有点的平面最近点对并返回其距离。考虑分治，记 $mid=\lfloor\frac{l+r}{2}\rfloor$，可以先进行 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid+1,r)$，考虑如何合并信息。

在记 $d$ 为 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid+1,r)$ 的较小值。容易发现我们仅需要考虑 $|x_i-x_{mid}|<d$ 的点（$x_i$ 为点 $i$ 的横坐标）。我们找出这些点，并将其按 $y$ 坐标排序。

之后我们暴力依次遍历这些点，对于遍历到的每个点，再往后暴力遍历直至 $y_j-y_i \ge d$ 为止。由 $d$ 的定义可以知道位于同一侧的点的距离一定 $\ge d$，再结合画图可以知道，每个点往后暴力遍历至多遍历 $7$ 个点，因此合并操作的复杂度为 $O(n)$。结合分治和每次进行的对 $y$ 排序，最终复杂度为 $O(n\log^2 n)$。

事实上，分治本质与归并排序相同，因此可以在分治过程中对 $y$ 进行排序，复杂度可以优化至 $O(n\log n)$，不过本代码中并没有实现。

代码

#include<bits/stdc++.h>
#define pi pair<int,int>
#define x first
#define y second
#define ll long long
using namespace std;
const int N=4e5+5;
int n;
pi a[N],b[N];
inline double dis(pi i,pi j){
    return sqrt((ll)(i.x-j.x)*(i.x-j.x)+(ll)(i.y-j.y)*(i.y-j.y));
}//计算距离
inline bool cmp(pi i,pi j){
    return i.y<j.y;
}
inline double solve(int l,int r){
    if(l==r) return 1e9;
    int mid=(l+r)>>1;
    double d=1e9;
    d=min(solve(l,mid),solve(mid+1,r));//分治计算
    int cnt=0;
    for(int i=l;i<=r;i++){//取出有用的点
        if(fabs(a[mid].x-a[i].x)<d) b[++cnt]=a[i];
    }
    sort(b+1,b+1+cnt,cmp);//对 y 排序
    for(int i=1;i<=cnt;i++){//暴力合并
        for(int j=i+1;j<=cnt;j++){
            if(b[j].y-b[i].y>=d) break;
            d=min(d,dis(b[i],b[j]));
        }
    }
    return d;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+1+n);//对 x 排序
    double ans=solve(1,n);
    printf("%.0lf\n",ans*ans);//最后输出平方
    return 0;
}