蒟蒻求助，刚学kdt，126分

按照oiwiki上的代码打的板子，前两个版本都过去了这个126分

评测记录

真心不知道哪里错了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#define int long long
#define lson tree[rt].ls
#define rson tree[rt].rs
using namespace std;
int n,rt,num[400010],ans=9e18;
struct node{
    int x,y;
}a[400010];
bool cmp1(node a,node b){
    return a.x<b.x;
}
bool cmp2(node a,node b){
    return a.y<b.y;
}
struct tr{
    int ls,rs,l,r,u,d;
}tree[400010];
int dis(int x,int y){
    return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
void maintain(int rt){
    tree[rt].l=tree[rt].r=a[rt].x;
    tree[rt].u=tree[rt].d=a[rt].y;
    if(lson){
        tree[rt].l=min(tree[rt].l,tree[lson].l);
        tree[rt].r=max(tree[rt].r,tree[lson].r);
        tree[rt].u=max(tree[rt].u,tree[lson].u);
        tree[rt].d=min(tree[rt].d,tree[lson].d);
    }
    if(rson){
        tree[rt].l=min(tree[rt].l,tree[rson].l);
        tree[rt].r=max(tree[rt].r,tree[rson].r);
        tree[rt].u=max(tree[rt].u,tree[rson].u);
        tree[rt].d=min(tree[rt].d,tree[rson].d);
    }
}
int build(int l,int r){
    if(l>=r)return 0;
    int mid=(l+r)>>1;
    double ax=0,ay=0,vx=0,vy=0;
    for(int i=l;i<=r;i++){
        ax+=a[i].x;ay+=a[i].y;
    }
    ax/=1.0*(r-l+1);ay/=1.0*(r-l+1);
    for(int i=l;i<=r;i++){
        vx+=(a[i].x-ax)*(a[i].x-ax);
        vy+=(a[i].y-ay)*(a[i].y-ay);
    }
    if(vx>=vy)num[mid]=1,nth_element(a+l,a+mid,a+r+1,cmp1);
    else num[mid]=2,nth_element(a+l,a+mid,a+r+1,cmp2);
    tree[mid].ls=build(l,mid-1);tree[mid].rs=build(mid+1,r);
    maintain(mid);
    return mid;
}
int f(int x,int y){
    int ret=0;
    if(tree[y].l>a[x].x)ret+=(tree[y].l-a[x].x)*(tree[y].l-a[x].x);
    if(tree[y].r<a[x].x)ret+=(a[x].x-tree[y].r)*(a[x].x-tree[y].r);
    if(tree[y].d>a[x].y)ret+=(tree[y].d-a[x].y)*(tree[y].d-a[x].y);
    if(tree[y].u<a[x].y)ret+=(a[x].y-tree[y].u)*(a[x].y-tree[y].u);
    return ret;
}
void query(int l,int r,int x){
    if(l>r)return;
    int mid=(l+r)>>1;
    if(mid!=x)ans=min(ans,dis(x,mid));
    if(l==r)return;
    int disl=f(x,tree[mid].ls),disr=f(x,tree[mid].rs);
    if(disl<ans&&disr<ans){
        if(disl<disr){
            query(l,mid-1,x);
            if(disr<ans)query(mid+1,r,x);
        }
        else{
            query(mid+1,r,x);
            if(disl<ans)query(l,mid-1,x); 
        }
    }
    else{
        if(disl<ans)query(l,mid-1,x);
        if(disr<ans)query(mid+1,r,x);
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
    build(1,n);
    for(int i=1;i<=n;i++)query(1,n,i);
    printf("%lld",ans);
    return 0;
}