要维护平面上点的信息,所以可以用KD-tree来维护,然后维护一个大小为(k)的堆,每次从根开始遍历,遇到一个点就看能不能作为前(k)远的点,也就是看能不能把堆中最近的点给替换掉.如果那个点在KD-tree上的控制区域中离要求的点的最远的点的距离比当前第(k)远距离小就不用访问了
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int nd;
struct point
{
int d[2],i;
bool operator < (const point &bb) const {return d[nd]!=bb.d[nd]?d[nd]<bb.d[nd]:i<bb.i;}
}a[N],b[N],qwq;
struct node
{
LL d;
int i;
bool operator < (const node &bb) const {return d!=bb.d?d>bb.d:i<bb.i;}
};
priority_queue<node> hp;
int n,m,rt,ch[N][2],mx[N][2],my[N][2],szz;
void bui(int &o,int l,int r,int nnd)
{
if(l>r) return;
if(l==r)
{
o=b[l].i;
mx[o][0]=mx[o][1]=a[o].d[0];
my[o][0]=my[o][1]=a[o].d[1];
return;
}
int mid=(l+r)>>1;
nd=nnd;
nth_element(b+l,b+mid,b+r+1);
o=b[mid].i;
mx[o][0]=mx[o][1]=a[o].d[0];
my[o][0]=my[o][1]=a[o].d[1];
bui(ch[o][0],l,mid-1,nnd^1);
bui(ch[o][1],mid+1,r,nnd^1);
mx[o][0]=min(mx[o][0],min(mx[ch[o][0]][0],mx[ch[o][1]][0]));
mx[o][1]=max(mx[o][1],max(mx[ch[o][0]][1],mx[ch[o][1]][1]));
my[o][0]=min(my[o][0],min(my[ch[o][0]][0],my[ch[o][1]][0]));
my[o][1]=max(my[o][1],max(my[ch[o][0]][1],my[ch[o][1]][1]));
}
LL dis(point aa,point bb){return 1ll*(aa.d[0]-bb.d[0])*(aa.d[0]-bb.d[0])+1ll*(aa.d[1]-bb.d[1])*(aa.d[1]-bb.d[1]);}
LL expt(int o)
{
if(!o) return -1;
LL xx=max(mx[o][1]-qwq.d[0],qwq.d[0]-mx[o][0]),yy=max(my[o][1]-qwq.d[1],qwq.d[1]-my[o][0]);
return xx*xx+yy*yy;
}
void wk(int o)
{
if(!o||expt(o)<hp.top().d) return;
node nw=(node){dis(a[o],qwq),o};
if(nw<hp.top()) hp.pop(),hp.push(nw);
if(expt(ch[o][0])>expt(ch[o][1])) wk(ch[o][0]),wk(ch[o][1]);
else wk(ch[o][1]),wk(ch[o][0]);
}
int main()
{
n=rd();
for(int i=1;i<=n;++i) a[i].d[0]=rd(),a[i].d[1]=rd(),a[i].i=i,b[i]=a[i];
mx[0][0]=my[0][0]=1<<30,mx[0][1]=my[0][1]=-(1<<30);
bui(rt,1,n,0);
m=rd();
while(m--)
{
qwq.d[0]=rd(),qwq.d[1]=rd();
int k=rd();
while(!hp.empty()) hp.pop();
while(k--) hp.push((node){-1,0});
//szz=0;
wk(rt);
node an=hp.top();
printf("%d
",an.i);
}
return 0;
}