完整代码:
```cpp
#include <algorithm>
#include <queue>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
typedef long double ldbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
typedef std::pair<llt,uint>Pair;
std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> >Q;
struct vec
{
llt x,y,v;vec(llt x=0,llt y=0,uint v=0):x(x),y(y),v(v){}
Pair len(){return Pair(x*x+y*y,v);}
friend vec operator-(vec a,vec b){return vec(a.x-b.x,a.y-b.y,a.v);}
};
typedef vec point;
struct kdt
{
struct node
{
point p,Max,Min;node*son[2];
~node()
{
if(son[0]!=NULL)delete son[0];
if(son[1]!=NULL)delete son[1];
}
voi build(point*Bgn,point*End,bol op)
{
uint len=End-Bgn;uint mid=len>>1;
std::nth_element(Bgn,Bgn+mid,End,[op](point a,point b)->bol{return op?a.x<b.x:a.y<b.y;});
Max=Min=p=Bgn[mid];
son[0]=son[1]=NULL;
if(len>1)
son[0]=new node,son[0]->build(Bgn,Bgn+mid,!op),
_max(Max.x,son[0]->Max.x),_max(Max.y,son[0]->Max.y),_min(Min.x,son[0]->Min.x),_min(Min.y,son[0]->Min.y);
if(len>2)
son[1]=new node,son[1]->build(Bgn+mid+1,End,!op),
_max(Max.x,son[1]->Max.x),_max(Max.y,son[1]->Max.y),_min(Min.x,son[1]->Min.x),_min(Min.y,son[1]->Min.y);
}
voi find(point w)
{
Q.push((p-w).len()),Q.pop();
if(son[0]!=NULL&&((son[0]->Max-w).len()>Q.top()||(son[0]->Min-w).len()>Q.top()
||(point(son[0]->Max.x,son[0]->Min.y)-w).len()>Q.top()||(point(son[0]->Min.x,son[0]->Max.y)-w).len()>Q.top()))
son[0]->find(w);
if(son[1]!=NULL&&((son[1]->Max-w).len()>Q.top()||(son[1]->Min-w).len()>Q.top()
||(point(son[1]->Max.x,son[1]->Min.y)-w).len()>Q.top()||(point(son[1]->Min.x,son[1]->Max.y)-w).len()>Q.top()))
son[1]->find(w);
std::swap(son[0],son[1]);
}
};
node*rot;
kdt(){rot=NULL;}
voi bzr()
{
if(rot!=NULL)delete rot;
rot=NULL;
}
voi build(point*Bgn,point*End){bzr(),rot=new node,rot->build(Bgn,End,1);}
voi find(point p){rot->find(p);}
};
bol Now[100005];
point P[100005];
kdt K;
int main()
{
uint n,m,k;point p;scanf("%u",&n);
for(uint i=0;i<n;i++)scanf("%lld%lld",&P[i].x,&P[i].y),P[i].v=n-i;
K.build(P,P+n);
scanf("%u",&m);
while(m--)
{
scanf("%lld%lld%u",&p.x,&p.y,&k);
while(!Q.empty())Q.pop();
while(k--)Q.push(Pair());
K.find(p);
printf("%u\n",n+1-Q.top().second);
}
return 0;
}
```
by myee @ 2021-11-04 09:29:27
stO 队爷 myee Orz
by _luanyi_ @ 2023-08-10 21:35:05