Lvat_s Blog

KD-Tree直接上

维护一个关于点对距离的数组

每次询问直接在KD-Tree里面贪心的找就可以了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int Sort_Tag,n,m,root,Ask_k,id[25];
long long Ask_x,Ask_y,ans[25];
 
struct KDTree{
long long d[2],mx[2],mn[2];
int l,r,id;
friend bool operator<(KDTree A,KDTree B){
return (A.d[Sort_Tag]<B.d[Sort_Tag])||(A.d[Sort_Tag]==B.d[Sort_Tag] && A.d[!Sort_Tag]<B.d[!Sort_Tag]);
}
}tree[N],Tp;
 
void Pushup(int rt){
if(tree[rt].l){
    if(tree[rt].mn[0]>tree[tree[rt].l].mn[0])tree[rt].mn[0]=tree[tree[rt].l].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].l].mn[1])tree[rt].mn[1]=tree[tree[rt].l].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].l].mx[0])tree[rt].mx[0]=tree[tree[rt].l].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].l].mx[1])tree[rt].mx[1]=tree[tree[rt].l].mx[1];
}
if(tree[rt].r){
    if(tree[rt].mn[0]>tree[tree[rt].r].mn[0])tree[rt].mn[0]=tree[tree[rt].r].mn[0];
    if(tree[rt].mn[1]>tree[tree[rt].r].mn[1])tree[rt].mn[1]=tree[tree[rt].r].mn[1];
    if(tree[rt].mx[0]<tree[tree[rt].r].mx[0])tree[rt].mx[0]=tree[tree[rt].r].mx[0];
    if(tree[rt].mx[1]<tree[tree[rt].r].mx[1])tree[rt].mx[1]=tree[tree[rt].r].mx[1];
}
}
 
int Build(int l,int r,int D){
int mid=l+r>>1;
Sort_Tag=D;
nth_element(tree+l+1,tree+mid+1,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 MxDist(int p,long long x,long long y){
return max(Sqr(tree[p].mx[0]-x),Sqr(tree[p].mn[0]-x))+max(Sqr(tree[p].mx[1]-y),Sqr(tree[p].mn[1]-y));
}
 
void Query(int rt){
long long Dl,Dr,Dm=Sqr(tree[rt].d[0]-Ask_x)+Sqr(tree[rt].d[1]-Ask_y);
int Kt=Ask_k;
while(Kt && ((ans[Kt]<Dm)||(ans[Kt]==Dm && id[Kt]>tree[rt].id)))Kt--;
if(Kt!=Ask_k){
    for(int i=Ask_k;i>=Kt+2;i--){
        ans[i]=ans[i-1];
        id[i]=id[i-1];
    }
    ans[Kt+1]=Dm;id[Kt+1]=tree[rt].id;
}
if(tree[rt].l)Dl=MxDist(tree[rt].l,Ask_x,Ask_y);else Dl=-1;
if(tree[rt].r)Dr=MxDist(tree[rt].r,Ask_x,Ask_y);else Dr=-1;
if(Dl<Dr){
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
}
else {
    if(Dl>=ans[Ask_k])Query(tree[rt].l);
    if(Dr>=ans[Ask_k])Query(tree[rt].r);
}
}
 
int main(){
freopen("2626.in","r",stdin);
freopen("2626.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lld %lld",&tree[i].d[0],&tree[i].d[1]);tree[i].id=i;}
root=Build(1,n,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
    scanf("%lld %lld %lld",&Ask_x,&Ask_y,&Ask_k);
    memset(ans,0,sizeof(ans));
    memset(id,127,sizeof(id));
    Query(root);
    printf("%d\n",id[Ask_k]);
}
return 0;
}