题解 P1257 【平面上的最接近点对】

w4p3r · 2019-03-21 17:18:16 · 题解

这不是KD-Tree板子吗，为啥没人写KD-Tree，那我来发一发KD-Tree的题解吧

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<bitset>
#define inf 1e100
#define eps 1e-6
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
struct node{double d[2],minn[2],maxn[2];int ch[2];}t[N<<1];
int n,rt,D;
double minn=inf;
double ansmin=inf;
double nowx,nowy;
inline int cmp(node x,node y){return x.d[D]<y.d[D];}
inline void pushup(int x)
{
    int l=t[x].ch[0],r=t[x].ch[1];
    if(l){t[x].maxn[0]=max(t[x].maxn[0],t[l].maxn[0]);t[x].maxn[1]=max(t[x].maxn[1],t[l].maxn[1]);t[x].minn[0]=min(t[x].minn[0],t[l].minn[0]);t[x].minn[1]=min(t[x].minn[1],t[l].minn[1]);}
    if(r){t[x].maxn[0]=max(t[x].maxn[0],t[r].maxn[0]);t[x].maxn[1]=max(t[x].maxn[1],t[r].maxn[1]);t[x].minn[0]=min(t[x].minn[0],t[r].minn[0]);t[x].minn[1]=min(t[x].minn[1],t[r].minn[1]);}
}
void build(int &root,int l,int r,int d)
{
    if(l>r){root=0;return ;}
    int mid=(l+r)>>1;D=d;root=mid;
    nth_element(t+l,t+mid,t+r+1,cmp);
    build(t[mid].ch[0],l,mid-1,d^1);
    build(t[mid].ch[1],mid+1,r,d^1);
    pushup(mid);
}
inline double dis(int x){return (t[x].d[0]-nowx)*(t[x].d[0]-nowx)+(t[x].d[1]-nowy)*(t[x].d[1]-nowy);}
inline double gmin(int x)
{
    double sum=0;
    if(t[x].maxn[0]<nowx){sum+=(nowx-t[x].maxn[0])*(nowx-t[x].maxn[0]);}
    if(t[x].minn[0]>nowx){sum+=(nowx-t[x].minn[0])*(nowx-t[x].minn[0]);}
    if(t[x].maxn[1]<nowy){sum+=(nowy-t[x].maxn[1])*(nowy-t[x].maxn[1]);}
    if(t[x].minn[1]>nowy){sum+=(nowy-t[x].minn[1])*(nowy-t[x].minn[1]);}
    return sum;
}
inline void qmin(int now)
{
    if(!now)return ;
    double len=dis(now),ls=gmin(t[now].ch[0]),rs=gmin(t[now].ch[1]);
    if(len>=eps){minn=min(minn,len);}
    if(ls<rs){if(ls<minn)qmin(t[now].ch[0]);if(rs<minn)qmin(t[now].ch[1]);}
    else {if(rs<minn)qmin(t[now].ch[1]);if(ls<minn)qmin(t[now].ch[0]);}
}
inline int Cmp(node x,node y){return x.d[0]<y.d[0]||(fabs(x.d[0]-y.d[0])<=eps&&x.d[1]<y.d[1]);}
int main()
{
    n=read();
    for(register int i=1;i<=n;i++)scanf("%lf%lf",&t[i].d[0],&t[i].d[1]),t[i].minn[0]=t[i].maxn[0]=t[i].d[0],t[i].minn[1]=t[i].maxn[1]=t[i].d[1];
    sort(t+1,t+n+1,Cmp);
    for(register int i=2;i<=n;i++)if(fabs(t[i].d[0]-t[i-1].d[0])<=eps&&fabs(t[i].d[1]-t[i-1].d[1])<=eps)ansmin=0;//特判，如果有两个点坐标相同就是0 
    build(rt,1,n,1);
    for(register int i=1;i<=n;i++)
    {
        nowx=t[i].d[0],nowy=t[i].d[1];
        minn=inf;qmin(rt);
        ansmin=min(ansmin,minn);
    }
    printf("%.4lf",sqrt(ansmin));
    return 0;
}