记录编号	454765	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	9.014 s
提交时间	2017-09-29 16:44:47	内存使用	2.60 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long L;
const L inf((L)1e16);
int now,n,m,k;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
struct point{
	L a[3];
	inline bool operator<(const point &b)const{
		return a[now]<b.a[now]||(a[now]==b.a[now]&&a[now^1]<b.a[now^1]);
	}
	L &operator[](int x){
		return a[x];
	}
}p[100005],cmp;
struct data{
	L dis,id;
	inline bool operator<(const data &a)const{
		return dis==a.dis?id<a.id:dis>a.dis;
	}
};
priority_queue<data>q;
inline L pf(L x){
	return x*x;
}
inline L dis(point x,point y){
	return pf(x[0]-y[0])+pf(x[1]-y[1]);
}
struct node{
	node *lch,*rch;
	point key;
	int mn[2],mx[2];
	node(point &x):key(x),lch(NULL),rch(NULL){
		mn[0]=mx[0]=x[0];
		mn[1]=mx[1]=x[1];
	}
	inline void pushup(node *x){
		if(x==NULL)
			return;
		mn[0]=min(mn[0],x->mn[0]),mn[1]=min(mn[1],x->mn[1]);
		mx[0]=max(mx[0],x->mx[0]),mx[1]=max(mx[1],x->mx[1]);
	}
	inline L cal_dis(){
		L ret(0);
		ret=max(ret,dis((point){mn[0],mn[1]},cmp));
		ret=max(ret,dis((point){mn[0],mx[1]},cmp));
		ret=max(ret,dis((point){mx[0],mn[1]},cmp));
		ret=max(ret,dis((point){mx[0],mx[1]},cmp));
		return ret;
	}
}*root;
inline void build(node *&rt,int l,int r,int d){
	if(l>r)
		return;
	int mid((l+r)>>1);
	now=d;
	nth_element(p+l,p+mid,p+r+1);
	rt=new node(p[mid]);
	build(rt->lch,l,mid-1,d^1);
	build(rt->rch,mid+1,r,d^1);
	rt->pushup(rt->lch);
	rt->pushup(rt->rch);
}
inline void query(node *rt){
	if(rt==NULL)
		return;
	if(q.size()==k&&rt->cal_dis()<q.top().dis)
		return;
	data ret((data){dis(rt->key,cmp),rt->key[2]});
	if(q.size()<k)
		q.push(ret);
	else
		if(ret<q.top())
			q.pop(),q.push(ret);
	L dis_l(rt->lch==NULL?inf:rt->lch->cal_dis());
	L dis_r(rt->rch==NULL?inf:rt->rch->cal_dis());
	if(dis_l>dis_r){
		query(rt->lch);
		if(dis_r>=q.top().dis||q.size()<k)
			query(rt->rch);
	}
	else{
		query(rt->rch);
		if(dis_l>=q.top().dis||q.size()<k)
			query(rt->lch);
	}
}
inline int gg(){
	freopen("jzpfar.in","r",stdin);
	freopen("jzpfar.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)
		p[i][0]=read(),p[i][1]=read(),p[i][2]=i;
	build(root,1,n,0);
	m=read();
	while(m--){
		cmp[0]=read(),cmp[1]=read(),k=read();
		while(!q.empty())
			q.pop();
		query(root);
		printf("%d\n",q.top().id);
	}
	return 0;
}
int K(gg());
int main(){;}