题解 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)$）。有：
$$\begin{aligned}
T(n)&=2T(n/2)+n\log n\cr &=4T(n/4)+n\log n+2(n/2)\log(n/2)\cr
&=4T(n/4)+2n\log n \cr
&=8T(n/8)+3n\log n \cr
&=\cdots \cr
&=n\log^2n
\end{aligned}$$
瓶颈在于每次合并答案时进行的排序。同样是分治思想，可以使用归并排序，在左右子区间的节点都排好序后，$\mathcal O(n)$ 地合并两个区间。此时总时间复杂度就是 $\mathcal O(n\log n)$ 了。
## 参考代码
```cpp
#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;
}
```