记录编号	484267	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	RealFan	是否通过	通过
代码语言	C++	运行时间	6.489 s
提交时间	2018-01-22 20:09:41	内存使用	12.91 MiB

#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e18
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define FO(i,a,b) for(int i=a;i<=b;++i)
#define FD(i,a,b) for(int i=a;i>=b;--i)
#define FE(i,G,x) for(int i=G.h[x];~i;i=G.v[i].nxt)
typedef long long LL;
 
 
template <class T> inline bool chkmin(T& x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T& x, T y) { return x < y ? x = y, true : false; }
 
inline LL read(void){
    LL x,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1; 
    for(x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
 
#define N 100005
#define MID (l+r>>1)
#define LS T[o].s[0]
#define RS T[o].s[1]
struct PII{
    LL dis;int id;  
    bool operator<(const PII& k) const{
        if(dis != k.dis)return dis > k.dis;
        return id < k.id;
    }
};
struct P{
	static int cur;
	int d[2],id;
	bool operator < (const P& o) const { return d[cur]<o.d[cur]; }
} a[N],Q;
int P::cur;
struct Seg{ int id,d[2],s[2],x[2],y[2]; } T[4*N];
priority_queue<PII> A;
int n,root,x,y,k;
 
void pushup(int x,int k){
	chkmin(T[x].x[0],T[k].x[0]);chkmax(T[x].x[1],T[k].x[1]);
	chkmin(T[x].y[0],T[k].y[0]);chkmax(T[x].y[1],T[k].y[1]);
}
 
inline LL sqr(LL x){ return x*x; }
LL dist(const P& x,const P& y){ return sqr(x.d[0]-y.d[0])+sqr(x.d[1]-y.d[1]); }
LL dist(const Seg& x){ 
	LL ans=0;
	ans+=max(sqr(x.x[0]-Q.d[0]),sqr(x.x[1]-Q.d[0]));
	ans+=max(sqr(x.y[0]-Q.d[1]),sqr(x.y[1]-Q.d[1]));
	return ans;
}
 
int build(int l,int r,int d){
	P::cur=d;int o=MID;
	nth_element(a+l,a+o,a+r+1);
	T[o].d[0]=T[o].x[0]=T[o].x[1]=a[o].d[0];
	T[o].d[1]=T[o].y[0]=T[o].y[1]=a[o].d[1];
	T[o].id=a[o].id;
	if (o!=l) LS=build(l,o-1,d^1),pushup(o,LS);
	if (o!=r) RS=build(o+1,r,d^1),pushup(o,RS);
	return o;
}
void query(int o,int d){
	LL tmp=dist(a[o],Q);
	if (tmp>A.top().dis||tmp==A.top().dis&&T[o].id<A.top().id) A.pop(),A.push(PII{tmp,T[o].id});
	LL ld=-oo,rd=-oo;
	if (LS) ld=dist(T[LS]);if (RS) rd=dist(T[RS]);
	if (ld>rd){
		if (LS&&A.top().dis<=ld) query(LS,d^1);
		if (RS&&A.top().dis<=rd) query(RS,d^1);
	}else{
		if (RS&&A.top().dis<=rd) query(RS,d^1);
		if (LS&&A.top().dis<=ld) query(LS,d^1);
	}
}
 
int main(void){
	freopen("jzpfar.in","r",stdin);
	freopen("jzpfar.out","w",stdout);
	n=read();FO(i,1,n) a[i].d[0]=read(),a[i].d[1]=read(),a[i].id=i;
	root=build(1,n,0);
	for (int q=read();q--;){
		x=read();y=read();k=read();
		assert(A.empty());
		FO(i,1,k) A.push(PII{0,-oo});  // bigger i smaller
		Q.d[0]=x;Q.d[1]=y;query(root,0);
		printf("%d\n",A.top().id);
		while (k--) A.pop();
	}
	return 0;
}