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

· · 题解

前言

现在的题解除了随机算法外只有两篇分治做法，一篇神仙用的蒟蒻看不懂的 vector，另一篇是 O(n\log^2n)，所以我献上一篇 O(n\log n) 的题解及代码。

解题思路

先按照 x 的大小分治,然后归并排序。

归并时按照 y 值。

然后步入难点：

假设我们已经求出了左半部分的最近距离和右半部分的最近距离，两个距离的较小值设为 d。

我们把划分左右两部分的中线的 x 值定为 midx。

很显然，最终的答案有三种情况：

  1. 两点在左半部分
  2. 两点在右半部分
  3. 一个点在左边，一个点在右边（即跨过中线）

我们已经求出了 1、2 两种情况，还剩第三种情况。

对于第三种情况，只有距离中线的距离 \leq x 的点才有可能成为最终答案。

所以我们在归并后，枚举一遍，找出所有 abs(x-midx)\leq d 的点，放入数组 q。

然后枚举一遍 q 数组，想一想另一个点可能在什么地方？答案只有两部分：

而且这两个点的 y 值的差一定小于 d。

而我们刚刚的归并排序就是按照 y 值排序的，所以当某个点 y 值的差大于 d 时，可以直接结束循环。

对于时间复杂度，可以证明符合条件的点很少（最多 6 个）。

所以总复杂度为 O(n\log n) 注：求 midx 时一定要在分治前面求，否则分治结束后会改变点在数组中的位置（因为是按照 y 值归并的）。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iomanip>
using namespace std;
const int maxn=400005;
int n;
struct Point{
    long long x,y;
}p[maxn],q[maxn];
bool cmp(const Point &a,const Point &b){
    return a.x<b.x;
}
long long dis(const Point &a,const Point &b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long divide(int l,int r){
    if(l==r) return 1ll<<62;
    int mid=(l+r)/2;
    long long midx=p[mid].x;
    long long d=min(divide(l,mid),divide(mid+1,r));
    int p1=l,p2=mid+1,tot=0;
    while(p1<=mid||p2<=r){
        if(p1<=mid&&(p2>r||p[p1].y<p[p2].y)){
            q[++tot]=p[p1++];
        }else{
            q[++tot]=p[p2++];
        }
    }
    for(int i=1;i<=tot;i++){
        p[l+i-1]=q[i];
    }
    tot=0;
    long long dd=d;
    d=sqrt(dd);
    for(int i=l;i<=r;i++){
        if(abs(p[i].x-midx)<=d) q[++tot]=p[i];
    }
    for(int i=1;i<=tot;i++){
        for(int j=i-1;j>=1&&q[i].y-q[j].y<=d;j--){
            dd=min(dd,dis(q[i],q[j]));
            d=sqrt(dd);
        }
    }
    return dd;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
    }
    sort(p+1,p+n+1,cmp);
    cout<<divide(1,n)<<endl;
    return 0;
}