kd-tree

 

#include
     
      #define lc (ch[x][0])#define rc (ch[x][1])#define ll long longusing namespace std;const int maxn=1e6+4;int n,m,cnt;ll mn[maxn][2],mx[maxn][2],ch[maxn][2],sz[maxn];int nthdir;priority_queue
      
       
        ,greater
        
          >q;inline ll sq(ll x){    return (ll)x*x;}struct Point{    ll pos[2];    ll& operator [](ll x){        return pos[x];    }    bool operator < (const Point &t) const {        return pos[nthdir] < t.pos[nthdir];    }    ll operator - (const Point &t) const {        return sq(abs(pos[0]-t.pos[0]))+sq(abs(pos[1]-t.pos[1]));    }    Point(int x,int y){        pos[0]=x;pos[1]=y;    }    Point(){};}p[maxn];inline void pushup(int x){    for(int i=0;i<=1;i++){        mn[x][i]=mx[x][i]=p[x][i];        if(lc){            mn[x][i]=min(mn[x][i],mn[lc][i]);            mx[x][i]=max(mx[x][i],mx[lc][i]);        }        if(rc){            mn[x][i]=min(mn[x][i],mn[rc][i]);            mx[x][i]=max(mx[x][i],mx[rc][i]);        }    }    sz[x]=sz[lc]+sz[rc]+1;}inline int build(int l,int r,int dir){    nthdir=dir;    int x=(l+r)>>1;    nth_element(p+l,p+x,p+r+1);    mn[x][0]=mx[x][0]=p[x][0];    mn[x][1]=mx[x][1]=p[x][1];    if(l
         
          x) rc=build(x+1,r,dir^1);    pushup(x);return x;}inline ll calc(int x,Point P){    return max(sq(mn[x][0]-P[0]),sq(mx[x][0]-P[0]))+max(sq(mn[x][1]-P[1]),sq(mx[x][1]-P[1]));}inline void query(int x,Point P){    ll h=P-p[x];    if(h>q.top()){        q.pop();        q.push(h);    }    ll l=0,r=0;    if(lc) l=calc(lc,P);    if(rc) r=calc(rc,P);    if(l>r){        if(l>q.top()) query(lc,P);        if(r>q.top()) query(rc,P);    }else{        if(r>q.top()) query(rc,P);        if(l>q.top()) query(lc,P);    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%d%d",&p[i][0],&p[i][1]);    cnt=n;    int rt=build(1,n,0);    for(int i=1;i<=m*2;i++) q.push(0);    for(int i=1;i<=n;i++){        query(rt,p[i]);    }    cout<