记录编号	434311	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]JZPFAR	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	9.259 s
提交时间	2017-08-07 17:49:31	内存使用	2.60 MiB

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using std::max;
using std::min;
typedef long long ll;
const ll inf = (ll)1e16;
const int MAXN = 100005;
int now,n,m,k;


template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return x*f;
}

struct Point{
    ll 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]);
    }
    ll &operator [](int x){return a[x];}
}pt[MAXN],cmp;

struct res{
    ll dis,id;
    bool operator < (const res & a)const{
        return dis == a.dis? id < a.id : dis > a.dis;
    }
};
std::priority_queue<res>Q;

inline ll sqr(ll x){return x*x;}
inline ll dis(Point x,Point y){return sqr(x[0]-y[0])+sqr(x[1]-y[1]);}

struct node{
    node *ls,*rs;
    Point point;
    int mn[2],mx[2];
    node(Point &x){
        point = x;
        ls = rs = NULL;
        mn[0]=mx[0]=x[0];
        mn[1]=mx[1]=x[1];
    }
    inline void Maintain(node *x){
        if(x==NULL)return;
        for(int i=0;i<=1;i++)mn[i]=min(mn[i],x->mn[i]);
        for(int i=0;i<=1;i++)mx[i]=max(mx[i],x->mx[i]);
    }
    inline ll calc_dis(){
        ll Ans = 0;
        Ans = max(Ans,dis((Point){mn[0],mn[1]},cmp));
        Ans = max(Ans,dis((Point){mn[0],mx[1]},cmp));
        Ans = max(Ans,dis((Point){mx[0],mn[1]},cmp));
        Ans = max(Ans,dis((Point){mx[0],mx[1]},cmp));
        return Ans;
    }
}*root;

void build(node *&o,int l,int r,int d){
    if(l>r)return;
    int mid = l+r>>1;
    now = d;std::nth_element(&pt[l],&pt[mid],&pt[r+1]);
    o = new node(pt[mid]);
    build(o->ls,l,mid-1,d^1);
    build(o->rs,mid+1,r,d^1);
    o->Maintain(o->ls);
    o->Maintain(o->rs);
}

inline void Query(node *rt){
    if(rt==NULL)return;
    if(Q.size()==k&&rt->calc_dis()<Q.top().dis)return;
    res ans = (res){dis(rt->point,cmp),rt->point[2]};
    if(Q.size()<k)Q.push(ans);
    else if(ans<Q.top())Q.pop(),Q.push(ans);//这个东西重载了QAQ。。
    ll dis_ls = rt->ls==NULL?inf:rt->ls->calc_dis();
    ll dis_rs = rt->rs==NULL?inf:rt->rs->calc_dis();
    if(dis_ls>dis_rs){
        Query(rt->ls);
        if(dis_rs>=Q.top().dis||Q.size()<k)Query(rt->rs);
    }
    else{
        Query(rt->rs);
        if(dis_ls>=Q.top().dis||Q.size()<k)Query(rt->ls);
    }
}

int main(){
    freopen("jzpfar.in","r",stdin);
    freopen("jzpfar.out","w",stdout);
    n=read<int>();
    for(int i=1;i<=n;++i)pt[i][0]=read<int>(),pt[i][1]=read<int>(),pt[i][2]=i;
    build(root,1,n,0);
    m=read<int>();
    for(int i=1;i<=m;++i){
        cmp[0]=read<int>();cmp[1]=read<int>();
        k=read<int>();
        while(!Q.empty())Q.pop();
        Query(root);
        printf("%d\n",Q.top().id);
    }
}