BUPT2017 wintertraining(15) #5E
这题是裸的kdtree。 kdtree就是k-dimension tree的缩写,是一种分割k维数据空间的数据结构,可用来多维空间数据的范围搜索和最近邻搜索。 这题只是求2维的最近的点,代码比较短。以下是我对算法的理解:
其它就是,注意最近点不能是本身,nd初始值为0,nd0则一定要更新,否则若md0则不能拿来更新nd。
#include<cstdio>
#include<algorithm>
#define N 100005
#define ll long long
using namespace std;
struct point{
int x[2];
}a[N],b[N];
ll nd;
int t,n,now;
bool cmp(point a,point b){return a.x[now] < b.x[now];}
ll sqr(int x){return (ll)x*x;}
ll dis(point a,point b){return sqr(a.x[0]-b.x[0])+sqr(a.x[1]-b.x[1]);}
void build(int l,int r,int d){
if(l>=r) return;
int m=l+r>>1;
now=d;
nth_element(a+l,a+m,a+r,cmp);
build(l,m,d^1);
build(m+1,r,d^1);
}
void query(int l,int r,int d,point p){
if(l>=r)return;
int m=l+r>>1,sl=l,sr=m;
ll md=dis(a[m],p);
if(nd==0||md&&nd>md)nd=md;
if(p.x[d]>a[m].x[d])sl=m+1,sr=r;
query(sl,sr,d^1,p);
if(nd>sqr(a[m].x[d]-p.x[d]))
query(l+m+1-sl,m+r-sr,d^1,p);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",a[i].x,a[i].x+1),b[i]=a[i];
build(0,n,0);
for(int i=0;i<n;i++)
nd=0,query(0,n,0,b[i]),printf("%lld\n",nd);
}
return 0;
}