记录编号	225992	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	14.691 s
提交时间	2016-02-17 18:48:29	内存使用	1.45 MiB

#define null NULL
#define maxn 100010ul

#define ll long long

#include <queue>
#include <stdio.h>
#include <algorithm>

struct Point{
	int d[3];
	int& operator [](const int x){return d[x];}
}sp[maxn],cp;

struct res{
	ll dis;int id;
	friend bool operator < (res a,res b){return a.dis>b.dis||(a.dis==b.dis&&a.id<b.id);}
};

int n,q,cur,K;
const ll inf=1e16;

inline ll sqr(ll x){return x*x;}
inline ll dis(Point x,Point y){return sqr((ll)x[0]-(ll)y[0])+sqr((ll)x[1]-(ll)y[1]);}
inline bool cmp(Point a,Point b){return a[cur]<b[cur]||(a[cur]==b[cur]&&a[cur^1]<b[cur^1]);}
inline ll Min(ll a,ll b){return a<b?a:b;}
inline ll Max(ll a,ll b){return a>b?a:b;}

struct node{
	node *left,*right;
	Point point;
	int min_limit[2],max_limit[2];
	node(Point &x){
		point=x;
		left=right=null;
		min_limit[0]=max_limit[0]=x[0];
		min_limit[1]=max_limit[1]=x[1];
		return;
	}
	inline void update(node *&x){
		if(x==null) return;
		for(int i=0;i<2;i++) min_limit[i]=Min(min_limit[i],x->min_limit[i]);
		for(int i=0;i<2;i++) max_limit[i]=Max(max_limit[i],x->max_limit[i]);
		return;
	}
	inline ll max_dis(){
		ll res=0;
		res=Max(res,dis((Point){min_limit[0],min_limit[1]},cp));
		res=Max(res,dis((Point){min_limit[0],max_limit[1]},cp));
		res=Max(res,dis((Point){max_limit[0],min_limit[1]},cp));
		res=Max(res,dis((Point){max_limit[0],max_limit[1]},cp));
		return res;
	}
}*root;

std::priority_queue<res> que;

inline void build(node *&rt,int l,int r,int d){
	if(l>r) return;
	int mid=(l+r)>>1;
	cur=d,std::nth_element(sp+l+1,sp+mid+1,sp+r+1,cmp);
	rt=new node(sp[mid]);
	build(rt->left,l,mid-1,d^1);
	build(rt->right,mid+1,r,d^1);
	rt->update(rt->left);
	rt->update(rt->right);
	return;
}

inline void ask(node *rt){
	if(rt==null) return;
	if(que.size()==K&&rt->max_dis()<que.top().dis) return;
	res ret=(res){dis(cp,rt->point),rt->point[2]};
	if(que.size()<K) que.push(ret);
	else if(ret<que.top()) que.pop(),que.push(ret);
	ll disL=rt->left!=null?rt->left->max_dis():inf;
	ll disR=rt->right!=null?rt->right->max_dis():inf;
	if(disL>disR){
        ask(rt->left);
        if(disR>=que.top().dis) ask(rt->right);
	}
	else{
        ask(rt->right);
        if(disL>=que.top().dis) ask(rt->left);
	}
	return;
}

inline int in(){
	int x=0,c=getchar();bool flag=false;
	while(c<'0'||c>'9'){
        if(c=='-') flag=true;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(flag) return -x;
	return x;
}

inline int query(Point tmp){
	while(!que.empty()) que.pop();
	cp=tmp;ask(root);
	return que.top().id;
}

int main(){
	freopen("jzpfar.in","r",stdin);
	freopen("jzpfar.out","w",stdout);
 	n=in();
	for(int i=1;i<=n;i++) sp[i][0]=in(),sp[i][1]=in(),sp[i][2]=i;
	build(root,1,n,0);q=in();
	for(int i=1,x,y;i<=q;i++) x=in(),y=in(),K=in(),printf("%d\n",query((Point){x,y,0}));
	return 0;
}