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

有趣的分治呢 暴力的做法就是枚举两个点算距离更新答案 即使这样你也可以优化一下你的暴力 众所周知$sqrt$是一个跑得极慢的函数 所以我们可以两边平方消掉$sqrt$，最后再算一次即可 然后看分治做法.当然上面的技巧基本上可以用于带$sqrt$的所有题目. 先考虑降维~~打击~~，如果只有一维怎么做. 把所有点按照坐标排序，然后在中位数的位置画一条线，把点分成两个子集$P_1$和$P_2$. 我们只需要算出所有$p\in P_1,q\in P_2$的$min{dis(p,q)}$，然后递归地处理$P_1,P_2$即可. 如果直接暴力枚举两边的点，那么复杂度$f(n)=2f(n/2)+O(n^2)=O(n^2\log n)$，变差了，所以不可以这么做. 现在假设两个子集的答案已经求出，那么我们设$d=min(solve(P_1),solve(P_2))$,中位数的坐标是$m$，那么我们只需要处理所有坐标在$[m-d,m+d]$范围内的点即可。容易看出这样的点每边最多只有$2$个，否则他们它们之间的距离一定$<d$，矛盾，所以可以$O(1)$地处理，所以复杂度$f(n)=2f(n/2)+O(1)=O(n)$，考虑排序之后复杂度$O(n\log n)$ 现在把坐标变成二维，上面的做法应该对我们有一些启发性. 先按照$x$坐标排序，然后找一个中位$x$坐标$m$，在这里画一条平行于$y$轴的分割线，把点分成$P_1$和$P_2$两个子集.设两个子集的答案的较小值是$d$，那么我们处理的点一定是$x$坐标在$[m-d,m+d]$范围内，也就是两个竖直长条.但这次我们没这么幸运，因为这两个长条内的点还是$O(n)$的.我们来暴力地尝试一下: 把这个区域内的点按$y$坐标排序，然后枚举每一个点，从它往后枚举第二个点，如果这两个点的$y$坐标之差$>=d$那么就停止枚举第二个点. 然后你发现你$A$掉了这道题. 为什么呢?因为满足上述条件的第二个点在两边各最多有$6$个。所以复杂度是可以保证的.为什么是$6$个呢?这里给出证明. 显然对于每一个点，到它的距离$<d$的点在每一边一定会落在一个$d\times2d$的矩形之内(其实是个半径为$d$的圆，但是圆难以处理，所以用矩形近似).这个矩形内的点需要满足两两之间的距离$>=d$.这样的点如果$>6$个，那么我们用鸽巢原理:把$d\times 2d$的矩形切成6个$\dfrac{1}{2}d\times\dfrac{2}{3}d$的小矩形，那么一定有两个或以上的点落在同一个小矩形内，但是这个小矩形中两点的最大距离等于对角线长，也就是$\dfrac{5}{6}d<d$，矛盾.因此最多只有六个点。 于是我们枚举每一个点，找这些点就可以了 到这里算法已经明确，但实现上出现了一些问题: 1. 如果你合并答案用$stl$的$sort$，那么复杂度$f(n)=2f(n/2)+O(nlogn)=O(n\log^2n)$就不对了.我们需要归并排序.这样我们就不可能只对两个长条内的点排序，而是需要对所有正在处理的区间内的点排序了.归并的复杂度也是基于递归的，并且处理子问题的时候两个序列已经有序，所以归并排序可以把总时间复杂度减小到$O(n\log n)$.但是这道题数据水，所以$sort$可以取得更加优秀的效率.说一下怎么卡:所有的点全都在一条直线上，就可以把$sort$卡到极限. 2. $sort$有一个好处:它可以只把两个长条内的点提出来排序，对于随机数据效率优秀. $sort$的代码可以去看其他题解，这里放出归并的代码. ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct Point{int x,y;}a[2000000],tmp[2000000]; int n,b[2000000]; const long long inf=5e18; long long sqr(int x){return (long long)x*x;} long long dis(int l,int r){return sqr(a[l].x-a[r].x)+sqr(a[l].y-a[r].y);} int cmp(const Point &a,const Point &b){return a.x==b.x?a.y<b.y:a.x<b.x;} void merge(int l,int r) { int mid=(l+r)>>1,i=l,j=mid+1;//归并 for(int k=l;k<=r;k++) { if(i<=mid&&(j>r||a[i].y<a[j].y))tmp[k]=a[i++]; else tmp[k]=a[j++]; } for(int i=l;i<=r;i++)a[i]=tmp[i]; } long long solve(int l,int r) { if(l>=r)return inf; if(l+1==r){if(a[l].y>a[r].y)swap(a[l],a[r]);return dis(l,r);} int mid=(l+r)>>1,t=a[mid].x,cnt=0;//重新排序后中位数就乱了，需要记下来 long long d=min(solve(l,mid),solve(mid+1,r)); merge(l,r); for(int i=l;i<=r;i++) if(sqr(a[i].x-t)<d)//两边平方的技巧 b[++cnt]=i;//区间内的拉出来处理 for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt&&sqr(a[b[j]].y-a[b[i]].y)<d;j++) d=min(d,dis(b[j],b[i])); 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+n+1,cmp); printf("%.4lf",sqrt(solve(1,n))); } ```