P1429 平面最近点对（加强版）

题目

P1429 平面最近点对（加强版）

做法

Orz远古P党神犇

分治计算点对，先按\(x,y\)顺序排一下然后计算

主要考虑如何合并，已得到的答案为\(d\)，两块的点都算过了，只用计算被分裂的点，距离中轴\(<d\)把这些点记录一下按\(y\)排序

根据简单的证明一个点能与最多六个点计算，确保了时间复杂度

My complete code

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
using namespace std;
typedef int LL;
const LL maxn=1e6;
const double inf=100000000000.0;
struct node{
    double x,y;
}a[maxn];
LL n; LL tmp[maxn];
inline bool cmp1(node x,node y){
    return (x.x<y.x)||(x.x==y.x&&x.y<y.y);
}
inline bool cmp2(LL x,LL y){
    return a[x].y<a[y].y;
}
inline double Calc(LL x,LL y){
    return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
double Solve(LL l,LL r){
    if(l==r) return inf;
    if(l+1==r) Calc(l,r);
    double d(inf); LL mid(l+r>>1);
    d=min(d,min(Solve(l,mid),Solve(mid+1,r)));
    LL tot(0);
    for(LL i=l;i<=r;++i)
        if(fabs(a[i].x-a[mid].x)<=d)
            tmp[++tot]=i;
    sort(tmp+1,tmp+1+tot,cmp2);
    for(LL i=1;i<=tot;++i)
        for(LL j=i+1;j<=tot&&a[tmp[j]].y-a[tmp[i]].y<d;++j)
            d=min(d,Calc(tmp[j],tmp[i]));
    return d;
}
int main(){
    scanf(" %d",&n);
    for(LL i=1;i<=n;++i) scanf(" %lf %lf",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp1);
    printf("%.4lf",Solve(1,n));
    return 0;
}