记录编号	132079	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	19.638 s
提交时间	2014-10-25 11:03:50	内存使用	9.88 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long LL;
const int SIZEN=100010;
class Point{
public:
	int id;
	int xy[2];
};
int cmp_index;//放全局这种写法丑爆了,但是放KD树类型里用static会编译错误......
bool operator < (const Point &a,const Point &b){//按照cmp_index这一维进行对比
	return a.xy[cmp_index]<b.xy[cmp_index];
}
LL sqrdis(Point a,Point b){//两点的平方距离
	return sqr((LL)(a.xy[0]-b.xy[0]))+sqr((LL)(a.xy[1]-b.xy[1]));
}
class KDT_Node{
public:
	int lson,rson;//左右儿子
	Point pt;//这个点
	int mx[2],mn[2];//矩形区域的四个边界
};
LL mx_sqrdis(KDT_Node a,Point p){//a的矩形区域到p的最远点,可以发现此最远点一定是矩形某顶点到p的距离
	LL x=max(abs(a.mx[0]-p.xy[0]),abs(a.mn[0]-p.xy[0]));
	LL y=max(abs(a.mx[1]-p.xy[1]),abs(a.mn[1]-p.xy[1]));
	return sqr(x)+sqr(y);
}
class Result{//某次查询返回的点,dis是平方距离
public:
	LL dis;
	int id;
	Result(LL a,int b):dis(a),id(b){}
};
bool operator < (const Result &a,const Result &b){
	return a.dis>b.dis||(a.dis==b.dis&&a.id<b.id);
}
class K_Dim_Tree{
public:
	int root;
	KDT_Node tree[SIZEN*4];
	int tot;
	priority_queue<Result> Q;//存放查询结果
	void query(Point p,int m,int x,int k){//求距离p的m远点,当前到了x,该以第k维切割
		KDT_Node &now=tree[x];
		Result tmp(sqrdis(now.pt,p),now.pt.id);//该点
		if(Q.size()<m) Q.push(tmp);
		else if(tmp<Q.top()) Q.pop(),Q.push(tmp);//如果比Q中最近点要远,就更新之
		int l=now.lson,r=now.rson;
		if(p.xy[k]<now.pt.xy[k]) swap(l,r);//先去尽量远的子块
		if(l!=-1&&(Q.size()<m||mx_sqrdis(tree[l],p)>=Q.top().dis))
			query(p,m,l,k^1);
		if(r!=-1&&(Q.size()<m||mx_sqrdis(tree[r],p)>=Q.top().dis))
			query(p,m,r,k^1);
	}
	int query(Point p,int m){
		while(!Q.empty()) Q.pop();
		query(p,m,root,0);
		return Q.top().id;
	}
	void update(int x){//根据两个子块计算矩形边界
		if(x==-1) return;
		KDT_Node &now=tree[x];
		if(now.lson!=-1)
			for(int i=0;i<2;i++)
				now.mn[i]=min(now.mn[i],tree[now.lson].mn[i]),
				now.mx[i]=max(now.mx[i],tree[now.lson].mx[i]);
		if(now.rson!=-1)
			for(int i=0;i<2;i++)
				now.mn[i]=min(now.mn[i],tree[now.rson].mn[i]),
				now.mx[i]=max(now.mx[i],tree[now.rson].mx[i]);
	}
	int build(Point s[],int l,int r,int k){//s[l]~s[r],当前应该分割第k维
		if(l>r) return -1;
		int x=tot++,mid=(l+r)/2;
		KDT_Node &now=tree[x];
		cmp_index=k;
		nth_element(s+l,s+mid,s+r+1);//保证s[mid]是中位数
		now.pt=s[mid];//s[mid]就是当前块的中心点
		for(int i=0;i<2;i++) now.mx[i]=now.mn[i]=s[mid].xy[i];
		now.lson=build(s,l,mid-1,k^1);
		now.rson=build(s,mid+1,r,k^1);
		update(x);
		return x;
	}
	void build(Point s[],int N){
		tot=0;
		root=build(s,1,N,0);
	}
}T;
int N,M;
Point P[SIZEN];
void work(void){
	Point now;
	int K;
	T.build(P,N);
	scanf("%d",&M);
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&now.xy[0],&now.xy[1],&K);
		printf("%d\n",T.query(now,K));
	}
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		P[i].id=i;
		scanf("%d%d",&P[i].xy[0],&P[i].xy[1]);
	}
}
int main(){
	freopen("jzpfar.in","r",stdin);
	freopen("jzpfar.out","w",stdout);
	read();
	work();
	return 0;
}