P1429

Aryper · 2021-07-28 11:27:14 · 个人记录

平面最近点对（加强版）

见识到了旋转的人类智慧，我受此启发，写了个暴力，然后跑过了。。。

其实就是先按横坐标排序，对每个点找横坐标距离最近的 100 个点暴力，再按纵坐标排序，对每个点找纵坐标距离最近的 100 个点暴力。其实很好卡，但是随机数据基本是卡不掉的。。。

然后是正经的分治。。。

先按横坐标第一优先，纵坐标第二优先的顺序排序。

然后取横坐标中位数的直线分开两个区域，接着在两个区域分别求最近点对，距离分别为 d_1,d_2 。

然后我们先取 d=\min\{d_1,d_2\} 。

然后找 [l,r] 中到中位数直线距离 \le d 的点，共计 cnt 个。

然后在这 cnt 个点里打暴力，保证在纵坐标之差 \ge d 时退出，至于这样为什么会更优，可以根据在同一边的点之间的距离 \ge d 和三角形的三边关系得证。然后就可以证明这个暴力可以看做 O(1) 。

时间复杂度 O(n\log n) 。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=5e5,inf=1e18;

struct node{
    ll x,y;
}a[N+5];

ll n;

ll tmp[N+5];

bool _cmp(ll x,ll y) {
    return a[x].y<a[y].y;
}

double dis(ll x,ll y) {
    return sqrt((double)(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 msort(ll l,ll r) {
    double d=inf;
    if(l==r) return d;
    if(l+1==r) return dis(l,r);
    ll mid=(l+r)/2;
    double d1=msort(l,mid),d2=msort(mid+1,r);
    d=min(d1,d2);
    ll cnt=0;
    for(ll i=l;i<=r;i++) {
        if(abs(a[mid].x-a[i].x)<d) {
            tmp[++cnt]=i;
        }
    }
    sort(tmp+1,tmp+cnt+1,_cmp);
    for(ll i=1;i<=cnt;i++) {
        for(ll j=i+1;j<=cnt&&a[tmp[j]].y-a[tmp[i]].y<d;j++) {
            double d3=dis(tmp[i],tmp[j]);
            if(d>d3) {
                d=d3;
            }
        }
    }
    return d;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

bool cmp(node x,node y) {
    return x.x==y.x?x.y<y.y:x.x<y.x;
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i].x=read();a[i].y=read();
    }

    sort(a+1,a+n+1,cmp);

    printf("%.4lf",msort(1,n));

    return 0;
}

代码：（人类智慧劣化版）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=5e5,inf=1e18;

struct node{
    ll x,y;
}a[N+5];

ll n,l,r,ans=inf,tmp;

double res;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

bool cmp(node x,node y) {
    return x.x<y.x;
}

bool _cmp(node x,node y) {
    return x.y<y.y;
}

ll max(ll x,ll y) {
    return x>y?x:y;
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i].x=read();a[i].y=read();
    }

    sort(a+1,a+n+1,cmp);

    for(ll i=1;i<=n;i++) {
        l=max(i-50,1);r=min(l+100,n);
        for(ll j=l;j<=r;j++) {
            if(j==i) continue;
            tmp=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
            ans=min(ans,tmp);
        }
    }

    sort(a+1,a+n+1,_cmp);

    for(ll i=1;i<=n;i++) {
        l=max(i-50,1);r=min(l+100,n);
        for(ll j=l;j<=r;j++) {
            if(j==i) continue;
            tmp=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
            ans=min(ans,tmp);
        }
    }

    res=(double)sqrt(ans);

    printf("%.4lf",res);

    return 0;
}