rt

提交记录

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define sq(x) (x)*(x)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
const int maxn=100005;
struct Point{ll d[2];}p[maxn];
struct Node{int ls,rs;ll mi[2],mx[2];Point val;}s[maxn];
int n,k,root,now,tot;
bool cmp(const Point&a,const Point&b){return a.d[now]<b.d[now];}
ll getDist(const Point&a,const Point&b)
    {return sq(a.d[0]-b.d[0])+sq(a.d[1]-b.d[1]);}
void maintain(int o){
    for(int i=0;i<2;i++){
        s[o].mi[i]=s[o].mx[i]=s[o].val.d[i];
        if(s[o].ls){
            s[o].mi[i]=min(s[o].mi[i],s[s[o].ls].mi[i]);
            s[o].mx[i]=max(s[o].mx[i],s[s[o].ls].mx[i]);
        }if(s[o].rs){
            s[o].mi[i]=min(s[o].mi[i],s[s[o].rs].mi[i]);
            s[o].mx[i]=max(s[o].mx[i],s[s[o].rs].mx[i]);
        }
    }
}
ll H(int o,const Point&x){
    ll dx=max(x.d[0]-s[o].mi[0],s[o].mx[0]-x.d[0]);
    ll dy=max(x.d[1]-s[o].mi[1],s[o].mx[1]-x.d[1]);
    return sq(dx)+sq(dy);
}

priority_queue<ll,vector<ll>,greater<ll> >ans;
int build(int L,int R,int d=0){
    if(L>R)return 0;
    int o=++tot;
    int M=(L+R)>>1;
    now=d;
    nth_element(p+L,p+M,p+R+1,cmp);
    s[o].val=p[M];
    s[o].ls=build(L,M-1,d^1);
    s[o].rs=build(M+1,R,d^1);
    maintain(o);
    return o;
}
void query(int o,const Point&x){
    if(!o)return;
    ll tmp=getDist(s[o].val,x);
    if(tmp>ans.top()){ans.pop();ans.push(tmp);}
    ll ql=H(s[o].ls,x),qr=H(s[o].rs,x);
    if(ql>=qr){
        if(ql>ans.top())query(s[o].ls,x);
        if(qr>ans.top())query(s[o].rs,x);
    }else{
        if(qr>ans.top())query(s[o].rs,x);
        if(ql>ans.top())query(s[o].ls,x);
    }
}

int main(){
    cin>>n>>k;k*=2;
    tot=0;
    for(int i=1;i<=k;i++)ans.push(0);
    for(int i=1;i<=n;i++)cin>>p[i].d[0]>>p[i].d[1];
    root=build(1,n);
    for(int i=1;i<=n;i++)query(root,p[i]);
    cout<<ans.top()<<endl;
    return 0;
}