kdt 0pts 求助/kel

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN(2e5+10);
int n;
struct node{double x,y;};
node p[MAXN];
inline bool cmp1(node x,node y){return x.x<y.x;}//按照 x 维度划分，重写 cmp
inline bool cmp2(node x,node y){return x.y<y.y;}//按照 y 维度划分，重写 cmp  
template<class T>
inline T Min(T x,T y){return x<y?x:y;}
template<class T>
inline T Max(T x,T y){return x>y?x:y;}
double ans(1e9);
struct KD_Tree
{
    bool type[MAXN];//0 维度为 x；1 维度为 y
    int lc[MAXN],rc[MAXN];//左孩子和右孩子 
    double minx[MAXN],miny[MAXN],maxx[MAXN],maxy[MAXN];
    inline void push_up(int u)//维护 x,y 的最大最小值 
    {
        minx[u]=maxx[u]=p[u].x,miny[u]=maxy[u]=p[u].y;
        if(lc[u])
        {
            minx[u]=Min(minx[u],minx[lc[u]]);
            miny[u]=Min(miny[u],miny[lc[u]]);
            maxx[u]=Max(maxx[u],maxx[lc[u]]);
            maxy[u]=Max(maxy[u],maxy[lc[u]]);
        }
        else
        {
            minx[u]=Min(minx[u],minx[rc[u]]);
            miny[u]=Min(miny[u],miny[rc[u]]);
            maxx[u]=Max(maxx[u],maxx[rc[u]]);
            maxy[u]=Max(maxy[u],maxy[rc[u]]);
        }
        return;
    }
    inline int build(int l,int r)//建树，返回值是这个子树中的根节点编号 
    {
        if(l>=r) return 0;
        int mid=(l+r)>>1;
        double avex(0),avey(0);//计算方差所需要的平均值 
        double sx(0),sy(0);//方差 
        for(register int i=l;i<=r;i++)
            avex+=p[i].x,avey+=p[i].y;
        avex/=(double)(r-l+1),avey/=(double)(r-l+1);//计算平均值
        for(register int i=l;i<=r;i++)
            sx+=(p[i].x-avex)*(p[i].x-avex),sy+=(p[i].y-avey)*(p[i].y-avey);
            //计算 x,y 两个维度的方差 
        if(sx>=sy)//对于方差大的维度进行划分 
        {
            type[mid]=false;
            nth_element(p+l,p+mid,p+r+1,cmp1);
        }
        else
        {
            type[mid]=true;
            nth_element(p+l,p+mid,p+r+1,cmp2);
        }
        lc[mid]=build(l,mid),rc[mid]=build(mid+1,r);
        push_up(mid);//维护子树内信息，不同题目不同分析 
        return mid; 
    } 
    inline double predic(int u,node pt)
    {
        double res(0);
        if(minx[u]>pt.x) res+=(minx[u]-pt.x)*(minx[u]-pt.x);
        if(maxx[u]<pt.x) res+=(maxx[u]-pt.x)*(maxx[u]-pt.y);
        if(miny[u]>pt.y) res+=(miny[u]-pt.y)*(miny[u]-pt.y);
        if(maxy[u]<pt.y) res+=(maxy[u]-pt.y)*(maxy[u]-pt.y);
        return res; 
    }
    inline double dis(node x,node y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
    inline void query(int l,int r,node pt,int idx)
    {
        if(l>r) return;
        int mid=(l+r)>>1;
        if(mid!=idx) ans=Min(ans,dis(pt,p[mid]));
        if(l==r) return;
        double dl=predic(lc[mid],pt),dr=predic(rc[mid],pt);
        if(dl<ans&&dr<ans)
        {
            if(dl<ans)
            {
                query(l,mid,pt,idx);
                if(dr<ans) query(mid+1,r,pt,idx);
            }
            else
            {
                query(mid+1,r,pt,idx);
                if(dl<ans) query(l,mid,pt,idx);
            }
        }
        else
        {
            if(dl<ans) query(l,mid,pt,idx);
            else query(mid+1,r,pt,idx);
        }
    }
};
KD_Tree kdt;
int main()
{
//  freopen("in1.txt","r",stdin); 
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    kdt.build(1,n);
    for(register int i=1;i<=n;i++)
        kdt.query(1,n,p[i],i);
    printf("%.4lf\n",ans);
    return 0;
}