题面不符？……
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, nowD, rot, din, kk;
const ll oo=9e18;
struct Point{
int d[2], mn[2], mx[2], id, idmin, l, r;
int & operator[](int x){
return d[x];
}
bool operator<(const Point &x)const{
return d[nowD]<x.d[nowD];
}
}p[100005], T;
struct QueryNode{
int idx;
ll dis;
QueryNode(int id=0, ll di=0){
idx = id;
dis = di;
}
}qn[25];
bool cmp(const QueryNode &x, const QueryNode &y){
if(x.dis!=y.dis) return x.dis>y.dis;
return x.idx<y.idx;
}
struct KDTree{
Point t[100005];
void pushUp(int k){
int l=t[k].l, r=t[k].r;
t[k].idmin = t[k].id;
if(l) t[k].idmin = t[l].idmin;
if(r) t[k].idmin = t[r].idmin;
for(int i=0; i<2; i++){
t[k].mn[i] = t[k].mx[i] = t[k][i];
if(l){
t[k].mn[i] = min(t[k].mn[i], t[l].mn[i]);
t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);
}
if(r){
t[k].mn[i] = min(t[k].mn[i], t[r].mn[i]);
t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);
}
}
}
int build(int l, int r, int now){
nowD = now;
int mid=(l+r)>>1;
nth_element(p+l, p+mid, p+r+1);
t[mid] = p[mid];
if(l<mid) t[mid].l = build(l, mid-1, now^1);
if(mid<r) t[mid].r = build(mid+1, r, now^1);
pushUp(mid);
return mid;
}
ll getDis(const Point &u, const Point &v){
return (ll)(u.d[0]-v.d[0])*(u.d[0]-v.d[0])+(ll)(u.d[1]-v.d[1])*(u.d[1]-v.d[1]);
}
ll calc(int x){
ll re=0;
for(int i=0; i<2; i++){
ll tmp=max(abs(t[x].mn[i]-T[i]), abs(t[x].mx[i]-T[i]));
re += tmp * tmp;
}
return re;
}
void query(int k){
int l=t[k].l, r=t[k].r;
ll dis=getDis(t[k], T), disl=-oo, disr=-oo;
if(dis>qn[1].dis || (dis==qn[1].dis && t[k].id<qn[1].idx)){
pop_heap(qn+1, qn+1+din, cmp);
qn[din] = QueryNode(t[k].id, dis);
// cout<<t[k].id<<" as t[k].id
";
push_heap(qn+1, qn+1+din, cmp);
}
if(l) disl = calc(l);
if(r) disr = calc(r);
if(disl>disr){
if(disl>qn[1].dis || (disl==qn[1].dis && t[l].idmin<qn[1].idx))
query(l);
if(disr>qn[1].dis || (disr==qn[1].dis && t[r].idmin<qn[1].idx))
query(r);
}
else{
if(disr>qn[1].dis || (disr==qn[1].dis && t[r].idmin<qn[1].idx))
query(r);
if(disl>qn[1].dis || (disl==qn[1].dis && t[l].idmin<qn[1].idx))
query(l);
}
}
}kdt;
int main(){
cin>>n;
for(int i=1; i<=n; i++){
scanf("%d %d", &p[i][0], &p[i][1]);
p[i].id = p[i].idmin = i;
}
rot = kdt.build(1, n, 0);
cin>>m;
while(m--){
din = 0;
scanf("%d %d %d", &T[0], &T[1], &kk);
while(kk--) qn[++din] = QueryNode(0, -oo);
kdt.query(rot);
// while(din){
// // cout<<qn[1].dis<<" "<<qn[1].idx<<" as dis&idx
";
// pop_heap(qn+1, qn+1+din, cmp);
// din--;
// }
printf("%d
", qn[1].idx);
}
return 0;
}