题意：给定平面中的 (n) 个点，(m) 组询问，每次求距离给定点 ((px,py)) 第 (K) 远的点的编号，(nleq 1e5,m leq 1e4, Kleq 20)
题解：kd-tree + priority_queue
维护一个小根堆，堆顶是最近的点，or 相等距离点中编号最大的那个点。拿堆顶作为搜索时剪枝的依据：向下搜索当且仅当存在比堆顶更远的点，或存在与堆顶距离相等相等但是编号更小的点。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010; const ll Inf=8e18;
int n,m,D,rt;
struct P { int d[2],id;
inline bool operator < (const P& that) const
{return d[D]<that.d[D];}
}p[N],s;
struct node {
int mx[2],mn[2],dim,lc,rc,sum; P p;
#define ls (t[tr].lc)
#define rs (t[tr].rc)
#define dim(tr) (t[tr].dim)
#define mx(tr,i) (t[tr].mx[i])
#define mn(tr,i) (t[tr].mn[i])
#define P(tr,i) (t[tr].p.d[i])
#define s(tr) (t[tr].sum)
#define id(tr) (t[tr].p.id)
}t[N];
struct bide { int id; ll dis;
inline bool operator < (const bide& that) const
{return dis==that.dis?id<that.id:dis>that.dis;}
};
priority_queue<bide> q;
inline void upd(int tr,int dim) {
for(R i=0;i<2;++i) {
if(ls) mx(tr,i)=max(mx(tr,i),mx(ls,i)),mn(tr,i)=min(mn(tr,i),mn(ls,i));
if(rs) mx(tr,i)=max(mx(tr,i),mx(rs,i)),mn(tr,i)=min(mn(tr,i),mn(rs,i));
}
if(ls) s(tr)=min(s(tr),s(ls));
if(rs) s(tr)=min(s(tr),s(rs));
}
inline void build(int& tr,int l,int r,int dim) {
if(l>r) return ; R md=l+r>>1; tr=md;
D=dim,nth_element(p+l,p+md,p+r+1);
t[tr].p=p[md]; s(tr)=id(tr);
for(R i=0;i<2;++i) mn(tr,i)=mx(tr,i)=P(tr,i);
if(l<md) build(ls,l,md-1,dim^1);
if(md<r) build(rs,md+1,r,dim^1);
upd(tr,dim);
}
inline ll cal(const P& p)
{return (ll)(p.d[0]-s.d[0])*(p.d[0]-s.d[0])+(ll)(p.d[1]-s.d[1])*(p.d[1]-s.d[1]);}
inline ll cal1(const int& tr) {
register ll ret=0; for(R i=0;i<2;++i)
ret+=max((ll)(s.d[i]-mn(tr,i))*(s.d[i]-mn(tr,i)),(ll)(s.d[i]-mx(tr,i))*(s.d[i]-mx(tr,i)));
return ret;
}
inline void query(int tr) {
register ll dis=cal(t[tr].p),ldis=-Inf,rdis=-Inf;
if(dis>q.top().dis||(dis==q.top().dis&&id(tr)<q.top().id)) q.pop(),q.push((bide){id(tr),dis});
if(ls) ldis=cal1(ls); if(rs) rdis=cal1(rs);
if(ldis>rdis) {
if(ldis>q.top().dis||(ldis==q.top().dis&&s(ls)<q.top().id)) query(ls);
if(rdis>q.top().dis||(rdis==q.top().dis&&s(rs)<q.top().id)) query(rs);
} else {
if(rdis>q.top().dis||(rdis==q.top().dis&&s(rs)<q.top().id)) query(rs);
if(ldis>q.top().dis||(ldis==q.top().dis&&s(ls)<q.top().id)) query(ls);
}
}
inline void main() {
n=g(); for(R i=1;i<=n;++i)
p[i].d[0]=g(),p[i].d[1]=g(),p[i].id=i;
build(rt,1,n,0);
m=g(); for(R i=1,k;i<=m;++i) {
while(q.size()) q.pop();
s.d[0]=g(),s.d[1]=g(),k=g();
for(R i=1;i<=k;++i) q.push((bide){0,-Inf});
query(rt); printf("%d
",q.top().id);
}
}
} signed main() {Luitaryi::main(); return 0;}
2019.12.19