记录编号	160551	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	16.159 s
提交时间	2015-04-28 14:20:45	内存使用	12.98 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

#define LL long long
#define N 100010
#define sqr(x) ((x)*(x))

using namespace std;

void file(){
	freopen("jzpfar.in","r",stdin);
	freopen("jzpfar.out","w",stdout);
}

int D,n,m,K;

LL Abs(LL x){
	if(x<0LL) return -x;
	return x;
}

struct cpt{
	LL dis;
	int id;
	bool operator<(const cpt &a)const{
		if(dis!=a.dis) return dis>a.dis;
		return id<a.id;
	}
};

priority_queue<cpt> q;

struct node{
	LL x,y;
	int id;
	void scan(int i){
		scanf("%lld%lld",&x,&y);
		id=i;
	}
	bool operator<(const node &a)const{
		if(!D) return x<a.x;
		return y<a.y;
	}
}a[N];

LL dist(node a,node b){
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}

struct KD{
	LL minv[2],maxv[2];
	LL dis(node o){
		LL x=max(Abs(o.x-minv[0]),Abs(o.x-maxv[0]));
		LL y=max(Abs(o.y-minv[1]),Abs(o.y-maxv[1]));
		return sqr(x)+sqr(y);
	}
	KD operator+(const KD &a){
		KD c;
		c.minv[0]=min(minv[0],a.minv[0]);
		c.minv[1]=min(minv[1],a.minv[1]);
		c.maxv[0]=max(maxv[0],a.maxv[0]);
		c.maxv[1]=max(maxv[1],a.maxv[1]);
		return c;
	}
};

int ch[N<<1][2],tot;

#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define now tree[x]
#define ls tree[l(x)]
#define rs tree[r(x)]

struct KD_tree{
	node m;
	KD c;
}tree[N<<1];

int build(int l,int r,int k){
	int x=++tot;
	D=k;
	int mid=(l+r)>>1;
	nth_element(a+l,a+mid,a+r+1);
	now.m=a[mid];
	now.c.minv[0]=now.c.maxv[0]=now.m.x;
	now.c.minv[1]=now.c.maxv[1]=now.m.y;
	if(l<=mid-1){
		l(x)=build(l,mid-1,k^1);
		now.c=now.c+ls.c;
	}
	if(mid+1<=r){
		r(x)=build(mid+1,r,k^1);
		now.c=now.c+rs.c;
	}
	return x;
}

void ask(int x,node a,int k){
	cpt tmp=(cpt){dist(a,now.m),now.m.id};
	D=k;
	if(q.size()<K) q.push(tmp);
	else if(tmp<q.top()){
		q.pop();
		q.push(tmp);
	}
	int c1=l(x),c2=r(x);
	if(a<now.m) swap(c1,c2);
	if(c1 && (q.size()<K || now.c.dis(a)>=q.top().dis)) ask(c1,a,k^1);
	if(c2 && (q.size()<K || now.c.dis(a)>=q.top().dis)) ask(c2,a,k^1);
}

int main(){
	file();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) a[i].scan(i);
	build(1,n,0);
	scanf("%d",&m);
	node tmp;
	for(int i=1;i<=m;i++){
		tmp.scan(i);
		scanf("%d",&K);
		while(!q.empty()) q.pop();
		ask(1,tmp,0);
		printf("%d\n",q.top().id);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}