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

2021hych · 2022-03-04 20:54:35 · 题解

直接看思路：

很明显，求的是给定的点集中，距离最近的两个点的距离的平方。首先根据这道题被评为蓝，便可知暴力就会挂（除非你充分发扬人类智慧）。当然了，这是个模板题，所以直接点明，分治题。

可以把它分一半平面内的最近点对 min1 和另一半平面内的最近点对 min2 。难道答案是 \min(min1,min2) 。显然不是，因为还要考虑跨越两个半平面的分界线的最近点对，再比较一下，这一部分线性扫描一下，来取出子点集。其他部分就是熟悉的递归了，不停地划分成两个子点集。一直到就剩一个点。

AC code:

#include<bits/stdc++.h>
#define inf 0x7f7f7f7f
#define maxn 400005
#define int long long
using namespace std;
int n;
struct node {
    double x,y;
}a[maxn],c[maxn];
bool cmp(node x,node y) {
    return x.x<y.x;
}
bool _cmp(node x,node y) {
    return x.y<y.y;
}
double GDX(int i,int j) {
    double dx=c[i].x-c[j].x,dy=c[i].y-c[j].y;
    return sqrt(dx*dx+dy*dy);
}
double work(int l,int r) {
    if(l==r) return inf;
    int mid=(l+r)/2;
    int num=0;
    double ans=min(work(l,mid),work(mid+1,r));
    for(int i=l;i<=r;i++) if(abs(a[mid].x-a[i].x)<=ans) c[++num]=a[i];
    sort(c+1,c+num+1,_cmp);
    for(int i=1;i<=num;i++)
        for(int j=i+1;j<=num;j++) {
            if(c[j].y-c[i].y>=ans) break;
            ans=min(ans,GDX(i,j));
        }
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    printf("%.0lf",pow(work(1,n),2));
    return 0;
}