Finding Hotels

在前车之鉴的基础上，真好，又是 1 A 1A 1A

题意：

在二维平面上给定 N N N个带权点； M M M个询问，每次询问最近的权值小于某一给定值的点。

思路：

  1. 依旧用K-D Tree进行暴力+剪枝。
  2. 首先将 N N N个点建好K-D Tree，然后对每个询问，暴力查询。
  3. 考虑K-D Tree的通用优化思想：对于某个根节点，在剪枝的情况下最好只遍历它的一个子树！
  4. 先搞定当前节点，然后看看询问节点在当前节点的考察维度的左边还是右边，然后就先遍历所在的那一边；关键剪枝： 如果询问点与当前点的考察维度的坐标差值就已经大于当前答案距离了，显然当前节点的另外一个子树（子空间）就不需要遍历了！毕竟对于另外一个子空间考虑两个维度时，距离显然会大于当前答案距离了（这里讲的很绕，但画一下图就很清晰了）。
  5. 上述一个剪枝就可以直接AC了，这里还可以考虑另外一个剪枝进行加速：如果当前子空间的最小权值都大于给定权值，显然就不用进入啦。

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, M, Dim, tot, rt;
int ls[maxn], rs[maxn], mi[maxn];

struct P{
    int x[2], c, id;
    friend bool operator < (const P &a, const P &b) {
        return a.x[Dim]<b.x[Dim];
    }
    inline ll dis(const P &rhs) {
        return ll(x[0]-rhs.x[0])*(x[0]-rhs.x[0])+ll(x[1]-rhs.x[1])*(x[1]-rhs.x[1]);
    }
    void print() {
        cout<<x[0]<<" "<<x[1]<<" "<<c<<endl;
    }
}p[maxn], tmp[maxn], q;

pair<ll,P> ans;

void push_up(int now) {
    mi[now]=p[now].c;
    if(ls[now]) mi[now]=min(mi[now],mi[ls[now]]);
    if(rs[now]) mi[now]=min(mi[now],mi[rs[now]]);
}

void build(int l, int r, int dim, int &now) {
    if(l>r) { now=0; return; }
    now=++tot;
    int m=(l+r)/2;
    Dim=dim; nth_element(tmp+l,tmp+m,tmp+r+1); p[now]=tmp[m];
    build(l,m-1,dim^1,ls[now]); build(m+1,r,dim^1,rs[now]);
    push_up(now);
}

void query(int dim, int now) {
    if(!now) return;
    ll d0=p[now].dis(q);
    int lt=ls[now], rt=rs[now];
    if(q.x[dim]>=p[now].x[dim]) swap(lt,rt);
    if(ans.first==-1||d0<ans.first||(d0==ans.first&&p[now].id<ans.second.id)) {
        if(p[now].c<=q.c) ans.first=d0, ans.second=p[now];
    }
    if(lt&&mi[lt]<=q.c) query(dim^1,lt);
    ll tp=q.x[dim]-p[now].x[dim];
    if(rt&&mi[rt]<=q.c&&(ans.first==-1||tp*tp<=ans.first)) query(dim^1,rt);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    memset(mi,inf,sizeof(inf));
    int T; cin>>T;
    while(T--) {
        cin>>N>>M;
        for(int i=1; i<=N; ++i) cin>>tmp[i].x[0]>>tmp[i].x[1]>>tmp[i].c, tmp[i].id=i;
        tot=0; build(1,N,0,rt);
        for(int i=1; i<=M; ++i) {
            cin>>q.x[0]>>q.x[1]>>q.c;
            ans.first=-1;
            query(0,rt);
            ans.second.print();
        }
        for(int i=1; i<=N; ++i) ls[i]=rs[i]=0, mi[i]=inf;
    }
}