记录编号	160537	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	15.513 s
提交时间	2015-04-28 11:48:07	内存使用	1.45 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 1769. [国家集训队2012]JZPFAR
* ALG    : KD Tree 
* CMT    : 第二道KD_Tree  先自己yy一下吧...
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef double db ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
	ret[0]=0;while (CH=getchar() , CH<'!') ;
	while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
}

#include <algorithm>
#include <queue>

#define  maxt  500500LL
#define  maxn  100010LL
#define  infi  0x3f3f3f3fLL
#define  max(x,y) ((x)>(y)?(x):(y))
#define  min(x,y) ((x)<(y)?(x):(y))
#define  sqr(x) ((x)*(x))

struct P { int x,y,id ; } points[maxn] , tmp ;
struct ANS { ll dis;int id; } ;
bool operator < (const ANS&a,const ANS&b) { return a.dis==b.dis?a.id<b.id:a.dis>b.dis; }
/* 与<相反含义 */
inline ll ABS(const ll&x) { return x<0 ? -x : x; }
inline ll Dist(const P& a, const P& b) { return sqr((ll)a.x-b.x)+sqr((ll)a.y-b.y) ; }
/* 这里爆int了QAQ */
inline bool cmpx(const P& a, const P& b) { return a.x<b.x; }
inline bool cmpy(const P& a, const P& b) { return a.y<b.y; }

namespace KD_TREE {
	struct KD {
		KD *c[2]; P p;
		int x1,y1,x2,y2;
		inline void init(const P& a)
		{ x1=x2=a.x; y1=y2=a.y; p=a; }
		inline ll MaxDis(const P& a)
		{ return sqr(max(ABS(x1-a.x),ABS(x2-a.x)))+sqr(max(ABS(y1-a.y),ABS(y2-a.y))) ; }
		inline void Update(KD*a) ;
	}*null=new KD,*root;
	std::priority_queue<ANS>q;
	inline void KD::Update(KD *a) {
		if (a == null) return ;
		x1=min(a->x1,x1) ;
		x2=max(a->x2,x2) ;
		y1=min(a->y1,y1) ;
		y2=max(a->y2,y2) ;
	}
	/* 循环维度,d=0为以x分割 */
	void BuildTree(KD*&o,int L,int R,bool d) {
		if (L>R) { o=null;return; }
		std::sort(points+L+1,points+R+1,d?cmpy:cmpx) ;
		int M = L+(R-L)/2 ;
		o = new KD ; o->init(points[M]) ;
		BuildTree(o->c[0],L,M-1,d^1) ;
		BuildTree(o->c[1],M+1,R,d^1) ;
		o->Update(o->c[0]) ;
		o->Update(o->c[1]) ;
	}
	P qp ; int qk ;
	void Query(KD*o,bool d) {
		if (o == null) return ;
		ANS now=(ANS){Dist(qp,o->p),o->p.id} ;
		if (q.size()<qk) q.push(now) ;
		else if (now<q.top()) q.pop(),q.push(now) ;
		int First;
		if (d) First=(o->p.y>qp.y) ; else First=(o->p.x>qp.x) ;
		if (q.size()<qk || o->c[First]->MaxDis(qp)>=q.top().dis)
			Query(o->c[First],d^1) ;
		if (q.size()<qk || o->c[First^1]->MaxDis(qp)>=q.top().dis)
			Query(o->c[First^1],d^1) ;
	}
	void Query(const P& a,int K) {
		while (!q.empty()) q.pop() ;
		qp = a , qk = K ;
		Query(root,0) ;
		printf("%d\n",q.top().id) ;
	}
}

int main() {
int i , n , m , K ;
	#define READ
	#ifdef  READ
		freopen("jzpfar.in" ,"r",stdin ) ;
		freopen("jzpfar.out","w",stdout) ;
	#endif
	using namespace KD_TREE ;
	read(n) ;
	Rep (i,1,n) read(points[i].x),read(points[i].y),points[i].id=i;
	BuildTree(root,1,n,0);
	read(m) ;
	Rep (i,1,m) {
		read(tmp.x),read(tmp.y),read(K) ;
		Query(tmp,K) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}
/*
3
0 0
0 1
0 2
3
1 1 2
0 0 3
0 1 1
*/