分析
首先给大家推荐一个非常好的KDTree笔记 here
此题就是用优先队列维护距离最远的k个，最后输出队首元素即可
估价函数就是max和min两点到
询问点的最远距离
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
const int inf = 1e18;
struct kd {
int d[2],mx[2],mn[2],le,ri,id;
};
kd t[300100],now;
int n,m,root,wh;
inline bool operator < (kd a,kd b){
return a.d[wh]<b.d[wh];
}
struct node {
int d,id;
};
inline bool operator < (node a,node b){
return a.d>b.d||((a.d==b.d)&&(a.id<b.id));
}
inline void up(int rt){
for(int i=0;i<2;i++){
t[rt].mn[i]=min(t[rt].mn[i],min(t[t[rt].le].mn[i],t[t[rt].ri].mn[i]));
t[rt].mx[i]=max(t[rt].mx[i],max(t[t[rt].le].mx[i],t[t[rt].ri].mx[i]));
}
}
inline void build(int &x,int le,int ri,int wwh){
wh=wwh;
int mid=(le+ri)>>1;
x=mid;
nth_element(t+le,t+x,t+ri+1);
for(int i=0;i<2;i++)
t[x].mx[i]=t[x].mn[i]=t[x].d[i];
if(le<x)build(t[x].le,le,mid-1,wwh^1);
if(ri>x)build(t[x].ri,mid+1,ri,wwh^1);
up(x);
}
priority_queue<node>q;
inline int getd(kd a,kd b){
return (a.d[0]-b.d[0])*(a.d[0]-b.d[0])+(a.d[1]-b.d[1])*(a.d[1]-b.d[1]);
}
inline int calc(int x){
if(!x)return -inf;
int res=0;
for(int i=0;i<2;i++)
res+=max((t[x].mx[i]-now.d[i])*(t[x].mx[i]-now.d[i]),(t[x].mn[i]-now.d[i])*(t[x].mn[i]-now.d[i]));
return res;
}
inline void qurey(int x){
if(!x)return;
int dl=calc(t[x].le),dr=calc(t[x].ri),d=getd(t[x],now);
if(d>q.top().d||(d==q.top().d&&t[x].id<q.top().id)){
q.pop();
q.push((node){d,t[x].id});
}
if(dl>dr){
if(dl>=q.top().d)qurey(t[x].le);
if(dr>=q.top().d)qurey(t[x].ri);
}else {
if(dr>=q.top().d)qurey(t[x].ri);
if(dl>=q.top().d)qurey(t[x].le);
}
}
signed main(){
int i,j,k;
t[0].mn[0]=t[0].mn[1]=inf;
t[0].mx[0]=t[0].mx[1]=-inf;
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld%lld",&t[i].d[0],&t[i].d[1]);
t[i].id=i;
}
build(root,1,n,1);
scanf("%lld",&m);
for(i=1;i<=m;i++){
while(!q.empty())q.pop();
scanf("%lld%lld%lld",&now.d[0],&now.d[1],&k);
for(j=1;j<=k;j++)q.push((node){-1,-1});
qurey(root);
printf("%lld
",q.top().id);
}
return 0;
}