分析

一次过，非常爽。考虑 上的最近邻查询。虽然有人已经证明 上的最近邻查询时间复杂度会被构造数据卡到 。但是多数情况下是非常快的。那么这道题，只是把最近邻换成第 大距离。我们只需要用个堆来动态维护一下就好了。注意因为有编号的问题，所以要注意查询的小细节。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e5 + 100;
#define Pair pair<int,int>
struct Point{int p[2],id;}A[N];
bool cmp0(Point a,Point b) {return a.p[0] < b.p[0];}
bool cmp1(Point a,Point b) {return a.p[1] < b.p[1];}
struct Node{
    int mx[2],mi[2],p[2],ch[2],id;
}t[N];
int n,size,rt;
void pushup(int u) {
    int lc = t[u].ch[0],rc = t[u].ch[1];
    for(int i = 0;i < 2;i++) {
        t[u].mx[i] = t[u].mi[i] = t[u].p[i];
        if(lc) {
            t[u].mx[i] = max(t[u].mx[i],t[lc].mx[i]);
            t[u].mi[i] = min(t[u].mi[i],t[lc].mi[i]);
        }
        if(rc) {
            t[u].mx[i] = max(t[u].mx[i],t[rc].mx[i]);
            t[u].mi[i] = min(t[u].mi[i],t[rc].mi[i]);
        }
    }
} 
int build(int l,int r,int tpye) {
    if(r < l) return 0;
    int mid = l + r >> 1;
    if(tpye) nth_element(A+l,A+mid,A+r+1,cmp1);
    else nth_element(A+l,A+mid,A+r+1,cmp0);
    int u = ++size;
    t[u].p[0] = A[mid].p[0];t[u].p[1] = A[mid].p[1];t[u].id = A[mid].id;
    t[u].ch[0] = build(l,mid-1,1 - tpye);
    t[u].ch[1] = build(mid+1,r,1 - tpye);pushup(u);
    return u;
}
const int inf = 1e9;
priority_queue<Pair,vector<Pair>,greater<Pair> > heap;
int pow2(int x) {return x * x;}
int dist(int u,Point x) {
    if(!u) return -inf;
    int P1 = pow2(t[u].mx[0] - x.p[0]);
    int P2 = pow2(t[u].mi[0] - x.p[0]);
    int P3 = pow2(t[u].mx[1] - x.p[1]);
    int P4 = pow2(t[u].mi[1] - x.p[1]);
    return max(P1,P2) + max(P3,P4);
}
int dist(int x,int y,Point b) {
    return pow2(x-b.p[0]) + pow2(y-b.p[1]);
}
void ask(int u,Point x) {
    if(!u) return;
    int dis = dist(t[u].p[0],t[u].p[1],x);
    if(heap.top() < Pair(dis,-t[u].id)) heap.pop(),heap.push(Pair(dis,-t[u].id));
    int disl = dist(t[u].ch[0],x),disr = dist(t[u].ch[1],x);
    if(disl > disr) {
        if(disl >= heap.top().first) ask(t[u].ch[0],x);
        if(disr >= heap.top().first) ask(t[u].ch[1],x);
    }
    else {
        if(disr >= heap.top().first) ask(t[u].ch[1],x);
        if(disl >= heap.top().first) ask(t[u].ch[0],x);
    }
}
void print(int x) {
    if(!x) return;
    cout << x <<" "<<t[x].mi[0] <<" "<<t[x].mx[0] <<" "<<t[x].mi[1]<<" "<<t[x].mx[1]<< endl;
    print(t[x].ch[0]);print(t[x].ch[1]); 
}
signed main() {
    n = read();
    for(int i = 1;i <= n;i++) A[i].p[0] = read(),A[i].p[1] = read(),A[i].id = i;
    rt = build(1,n,0);
    //print(rt);
    int m = read();
    while(m--) {
        while(heap.size()) heap.pop();
        int x = read(),y = read(),k = read();
        for(int i = 1;i <= k;i++) heap.push(Pair(-1,0));
        ask(rt,(Point){x,y});
        printf("%lld\n", -heap.top().second);
    }
}