题解 P7883 【平面最近点对（加强加强版）】

囧仙 · 2021-10-01 18:04:15 · 题解

题目大意

给定平面上 n 个点，求出两点间欧几里得距离的最小值。

题解

由于本题是模板题，因此本题解尽量详细地讲述怎么使用分治法计算出平面最近点对的距离。一些奇技淫巧（比如随机旋转坐标系什么的），这里就不提了。

容易发现，坐标系上这些点的顺序并不会影响到最终的求解。因此可以先将所有的点按照 \bm x 坐标从小到大排序（如果两个点 x 坐标相同，那就随便排了）。接着使用分治法。

分治法的基本思路是，将大问题转化为类似的小问题，解决小问题后通过合并解决大问题。在本题中，我们要解决的问题就是计算标号为 0,1,2\cdots (n-1) 的这 n 个点的两点间最近距离。我们设计算标号为 l,l+1,\cdots (r-1) 的点的两点间最近距离为 \mathrm{Solve}(l,r)，本题即求 \mathrm{Solve}(0,n)。要想解决 \mathrm{Solve}(l,r)，可以考虑先解决 \mathrm{Solve}\left(l,\left\lfloor\frac{l+r}{2}\right\rfloor\right) 和 \mathrm{Solve}\left(\left\lfloor\frac{l+r}{2}\right\rfloor,r\right)。

容易发现，当 r=l+1 时不需要做任何处理（此时返回 ans=+\infty）。关键问题在于，如何合并两个子问题的结果。

这里生成了 9 个点作为例子：

按照 x 坐标排序后，从左往右依次为 P_1,P_7,P_3,P_2,P_8,P_4,P_9,P_5,P_6。将 \mathrm{Solve}(0,9) 转化为 \mathrm{Solve}(0,4) 和 \mathrm{Solve}(4,9)：

注意，这里使用的是左闭右开区间。因此 P_8 应该在蓝色部分，而非红色部分。

对于 \mathrm{Solve}(0,4)，可以进一步划分区间：

当红色部分被划分成了绿色部分和红色部分后，可以发现这两个子问题内都只有两个点了。因此直接更新最短距离 d\gets\min(d,\operatorname{dis}(P_1,P_7)),d\gets\min(d,\operatorname{dis}(P_2,P_3))，此时 d=\sqrt{5}。

下面考虑如何将绿色部分和红色部分的结果进行合并。也就是计算左边的点和右边的点相连对答案进行的更新。

将距离紫红色线段不超过 d 的点全部添加到当前需要处理的点内（显然，如果某个点到紫红色线段的距离已经超过了 d，那么它到另一侧节点的距离肯定是超过 d 的。可以剪枝剪去）。按照 \bm y 坐标从小到大考虑这些点之间产生的贡献。图中的绿色部分就是 P_1 需要考虑的点（对于 P_1 来说，y 坐标和它相差大于 d 的点也不用考虑了）。当然了，此时的绿色部分内没有任何的点，因此 P_1 在这一部分不会对答案进行更新。

处理完 P_1，就该处理 P_3 了。此时 P_2 进入到了绿色区域内。更新答案：d\gets\min(d,\operatorname{dis}(P_2,P_3))。

接着是处理 P_2。更新答案：d\gets\min(d,\operatorname{dis}(P_2,P_7))。

此时红色部分被完全处理完了。d=\sqrt 5。在上述过程中，我们暴力添加了所有到紫红色线段不超过 d 的点，并且按照 y 坐标从小到大进行处理。每个点的考虑范围就是 y 坐标到它不超过 d 的绿色矩形（上述例子没有出现绿色矩形内有多个点的情况。如果出现了多个点，需要依次连边进行答案的更新）。

处理完红色部分，再处理完蓝色部分，最后将橙色线段两侧距离不超过 d 的点按照 y 坐标排序后进行处理。最终得到答案为 2。

看上去这个做法在合并时是非常暴力的（因为一旦绿色部分内的点数非常多，就会导致复杂度退化）。但是可以证明，绿色部分内的点不超过 5 个：

考虑这样的一张图。容易发现，不可能会有某个点落入圆内，否则在合并之前求得的 d 会变得更小。在圆的四个角落内的点又最多只有 4 个，因此绿色部分的点的数目不超过 5。

现在假设我们已经给 [l,r) 内的点以 y 坐标为关键字排好了序。我们需要依次计算每个点对应的的绿色区域内有哪些点。容易发现，随着 y 坐标的升高，每次只会是绿色区域上面的点加入，只会是绿色区域底部的节点移出。因此可以使用双指针解决这种问题。

双指针对应了这样一种思想：

指针 L 和指针 R 之间是需要处理的数据。每次将 L 指针向右移动后，将 R 指针向右移动，直到拓展到需要处理的数据的右边界。容易发现，L 和 R 都只会移动最多 n 次，因此维护待处理数据的时间复杂度是 \mathcal O(n) 的。

考虑计算整个算法的时间复杂度。

设 T(n) 为解决 n 个点的时间复杂度。那么有 T(n)=2T(n/2)+n\log n（2T(n) 是分治解决子问题产生的代价；n\log n 则是按照 y 坐标排序；此外还需要使用双指针 \mathcal O(n) 地维护待处理数据；每个节点最多会与 5 个节点相连进行更新，因此这部分复杂度还是 \mathcal O(n)）。有：

瓶颈在于每次合并答案时进行的排序。同样是分治思想，可以使用归并排序，在左右子区间的节点都排好序后，\mathcal O(n) 地合并两个区间。此时总时间复杂度就是 \mathcal O(n\log n) 了。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
struct Point{int x,y;};
typedef vector<Point>::iterator Iter;
bool cmpx(const Point a,const Point b){return a.x<b.x;}
bool cmpy(const Point a,const Point b){return a.y<b.y;}
double dis(const Point a,const Point b){
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
void slv(const Iter l,const Iter r,double &d){
    if(r-l<=1) return;
    vector<Point> Q; Iter t=l+(r-l)/2;double w=t->x;
    slv(l,t,d),slv(t,r,d),inplace_merge(l,t,r,cmpy);
    for(Iter x=l;x!=r;++x)
        if(abs(w-x->x)<=d) Q.push_back(*x);
    for(Iter x=Q.begin(),y=x;x!=Q.end();++x){
        while(y!=Q.end()&&y->y<=x->y+d) ++y;
        for(Iter z=x+1;z!=y;++z) d=min(d,dis(*x,*z));
    }
}
vector<Point> X; int n; double ans=1e18;
int qrd(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int main(){
    n=qrd(); up(0,n-1,i){
        int x=qrd(),y=qrd(); X.push_back({x,y});
    }
    sort(X.begin(),X.end(),cmpx),slv(X.begin(),X.end(),ans);
    printf("%.0lf\n",ans*ans);
    return 0;
}