Description
给出n(n≤2×105)个二维平面上的点，每个点有权值c。m(m≤2×104)次询问，求所有权值小于等于c的点中，距离坐标(x,y)的欧几里得距离最小的点。如果有多个满足条件的点，输出最靠前的一个。
Solution
拿k-d树搞一搞就好啦。
如果一个子树代表的区域中所有点的权值都大于c，或者到所有点的距离都大于当前答案，就跳过不做。
Code
//Finding Hotels
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline char gc()
{
static char now[1<<16],*S,*T;
if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
return *S++;
}
inline int read()
{
int x=0; char ch=gc();
while(ch<'0'||'9'<ch) ch=gc();
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
return x;
}
typedef long long lint;
int const N=2e5+10;
lint const INF=1LL<<62;
int n,m;
int rt,ch[N][2];
struct point{lint c[3]; int id;} pt[N];
struct zone{lint c1[3],c2[3];} zn[N];
int D; bool cmpPt(point x,point y) {return x.c[D]<y.c[D];}
void create(int p)
{
for(int k=0;k<3;k++) zn[p].c1[k]=zn[p].c2[k]=pt[p].c[k];
ch[p][0]=ch[p][1]=0;
}
void update(int p)
{
for(int k=0;k<3;k++)
zn[p].c1[k]=min(pt[p].c[k],min(zn[ch[p][0]].c1[k],zn[ch[p][1]].c1[k])),
zn[p].c2[k]=max(pt[p].c[k],max(zn[ch[p][0]].c2[k],zn[ch[p][1]].c2[k]));
}
void build(int &p,int L,int R,int k0)
{
p=L+R>>1; create(p);
if(k0==3) k0=0; D=k0;
nth_element(pt+L,pt+p,pt+R+1,cmpPt);
if(L<p) build(ch[p][0],L,p-1,k0+1);
if(p<R) build(ch[p][1],p+1,R,k0+1);
update(p);
}
point A; int r; lint rDst;
lint dst(point B)
{
if(B.c[2]>A.c[2]) return INF;
return (A.c[0]-B.c[0])*(A.c[0]-B.c[0])+(A.c[1]-B.c[1])*(A.c[1]-B.c[1]);
}
lint dst(zone z)
{
if(z.c1[0]==INF||z.c1[2]>A.c[2]) return INF+1;
lint sum=0;
for(int k=0;k<2;k++)
{
lint d=0;
if(A.c[k]<z.c1[k]) d=z.c1[k]-A.c[k];
else if(z.c2[k]<A.c[k]) d=A.c[k]-z.c2[k];
sum+=d*d;
}
return sum;
}
void query(int p)
{
lint d=dst(pt[p]);
if(d<rDst||(d==rDst&&pt[p].id<pt[r].id)) r=p,rDst=d;
if(dst(zn[ch[p][0]])<=rDst) query(ch[p][0]);
if(dst(zn[ch[p][1]])<=rDst) query(ch[p][1]);
}
int main()
{
int task=read();
for(int k=0;k<3;k++) zn[0].c1[k]=INF,zn[0].c2[k]=-INF;
while(task--)
{
n=read(),m=read();
memset(pt,0,sizeof pt);
for(int i=1;i<=n;i++)
for(int k=0;k<3;k++) pt[i].c[k]=read();
for(int i=1;i<=n;i++) pt[i].id=i;
rt=0; build(rt,1,n,0);
for(int i=1;i<=m;i++)
{
for(int k=0;k<3;k++) A.c[k]=read();
r=0,rDst=INF,query(rt);
printf("%lld %lld %lld\n",pt[r].c[0],pt[r].c[1],pt[r].c[2]);
}
}
return 0;
}P.S.
要开long long哦。
55行在不合法时返回INF+1，是因为我懒得判断左右子树是否存在而这么写的。由于要求最靠前的点，所以dst()==rDst的时候也要做，但如果dst()由于不合法而返回INF的话，在rDst==INF的时候就会有问题，会去递归并不存在的子树从而出锅。其实先判断一下子树是否存在再做比较好，不容易出锅而且比较清晰。