CQOI 2016 k远点对

题目大意：n个点，求第k远的点对的距离

KD树裸题

注意要用堆维护第k远

#include<bits/stdc++.h>

#define ll unsigned long long

#define maxn 100010

using namespace std;

inline int read(){

    int s=;char ch=getchar();

    for(;ch<''||ch>'';ch=getchar());

    for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';

    return s;

}

int n,k,D,root;

struct node{

    ll d[],mn[],mx[],ls,rs;

    node(int x=,int y=){d[]=x;d[]=y;}

    ll & operator [] (int x){return d[x];}

    friend bool operator < (node a,node b){return a[D]<b[D];}

}a[maxn];

struct K{

    ll d;

    K(ll a=){d=a;}

};

priority_queue<K>Q;

bool operator < (K a,K b){return a.d>b.d;}

struct KD{

    node t[maxn],T;

    void up(int k){

        node l=t[t[k].ls],r=t[t[k].rs];

        for(int i=;i<;++i){

            t[k].mn[i]=t[k].mx[i]=t[k][i];

            if(t[k].ls)t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]);

            if(t[k].rs)t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]);

        }

    }

    int build(int l,int r,int now){

        D=now;int mid=(l+r)>>;

        nth_element(a+l,a+mid,a+r+);

        t[mid]=a[mid];

        if(l<mid)t[mid].ls=build(l,mid-,now^);

        if(r>mid)t[mid].rs=build(mid+,r,now^);

        up(mid);return mid;

    }

    ll dis(node a,node b){

        return (a[]-b[])*(a[]-b[])+(a[]-b[])*(a[]-b[]);

    }

    ll get(int k){

        if(!k)return ;

        ll L=;

        L=max(L,dis(T,node(t[k].mn[],t[k].mn[])));

        L=max(L,dis(T,node(t[k].mn[],t[k].mx[])));

        L=max(L,dis(T,node(t[k].mx[],t[k].mn[])));

        L=max(L,dis(T,node(t[k].mx[],t[k].mx[])));

        return L;

    }

    void ask(int k){

        if(!k)return;

        ll dl=get(t[k].ls),dr=get(t[k].rs);

        ll L=dis(T,t[k]);

        if(L>Q.top().d){Q.pop();Q.push(K(L));}

        if(dl>dr){

            if(dl>Q.top().d)ask(t[k].ls);

            if(dr>Q.top().d)ask(t[k].rs);

        }else{

            if(dr>Q.top().d)ask(t[k].rs);

            if(dl>Q.top().d)ask(t[k].ls);

        }

    }

    void work(){

        for(int i=;i<=n;++i){

            T=a[i];

            ask(root);

        }

    }

}kd;

int main(){

    n=read();k=read();k<<=;

    for(int i=;i<=n;++i)

        a[i][]=read(),a[i][]=read();

    root=kd.build(,n,);

    for(int i=;i<=k;++i)Q.push(K());

    kd.work();

    cout<<Q.top().d<<endl;

    return ;

}