Lvat_s Blog

这个题也是KD树搞一搞反正能过

（其实KD树复杂度不对）

最远直接做，K远那么就要搞一个堆来维护前k大值

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N=100005,K=105;
const long long INF=999999999999999ll;
 
int n,k,Sort_Tag,root;
priority_queue<long long,vector<long long>,greater<long long> > Q;
 
struct KDTree{
long long d[2],mx[2],mn[2];
int l,r;
friend bool operator<(KDTree A,KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
 
void Pushup(int rt){
if(tree[rt].l){
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
}
if(tree[rt].r){
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
}
}
 
int Build(int l,int r,int D){
Sort_Tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mx[0]=tree[mid].mn[0]=tree[mid].d[0];
tree[mid].mx[1]=tree[mid].mn[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
long long Sqr(long long x){return x*x;}
long long Dist(KDTree A,KDTree B){return Sqr(A.d[0]-B.d[0])+Sqr(A.d[1]-B.d[1]);}
long long MxDist(KDTree A,KDTree B){return max(Sqr(A.mn[0]-B.d[0]),Sqr(A.mx[0]-B.d[0]))+max(Sqr(A.mn[1]-B.d[1]),Sqr(A.mx[1]-B.d[1]));}
 
void Solve(int rt){
long long Dl=-INF,Dr=-INF,Dm=Dist(tree[rt],Temp);
if(Dm>Q.top())Q.pop(),Q.push(Dm);
if(tree[rt].l)Dl=MxDist(tree[tree[rt].l],Temp);
if(tree[rt].r)Dr=MxDist(tree[tree[rt].r],Temp);
if(Dl>Dr){
    if(Dl>=Q.top())Solve(tree[rt].l);
    if(Dr>=Q.top())Solve(tree[rt].r);
}
else {
    if(Dr>=Q.top())Solve(tree[rt].r);
    if(Dl>=Q.top())Solve(tree[rt].l);
}
}
 
int main(){
freopen("4520.in","r",stdin);
freopen("4520.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld %lld",&tree[i].d[0],&tree[i].d[1]);
root=Build(1,n,0);
for(int i=1;i<=2*k;i++)Q.push(0);
for(int i=1;i<=n;i++){
    Temp.d[0]=tree[i].d[0];
    Temp.d[1]=tree[i].d[1];
    Solve(root);
}
printf("%lld\n",Q.top());
return 0;
}