本文共 1724 字，大约阅读时间需要 5 分钟。
分析
首先给大家推荐一个非常好的KDTree笔记
此题就是y9ong优先队列维护距离最远的k个，最后输出队首元素即可
估价函数就是max和min两点到
询问点的最远距离
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define int long longconst 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||((a.d==b.d)&&(a.id >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].ri,mid+1,ri,wwh^1); up(x);}priority_queue 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 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\n",q.top().id); } return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/10562702.html