问题描述:
平面最近邻居问题。已知平面上n个点的坐标，求每个点的最近邻居。
| 输入：有多个测试。第 1 行输入正整数 T，表示 T 个测试，T ≤ 15。每个测试的第 1 行输入整数 n，2 ≤ n ≤ 105；后面 n 行中，每行输入两个整数，表示坐标。n个点不重合。 |
| 输出：对每个测试输出 n 行，其中第 i 行输出第 i 个点到最近邻居的距离的平方。 |
| 输入样例 | 输出样例 |
| 2 10 17 41 0 34 24 19 8 28 14 12 45 5 27 31 41 11 42 45 36 27 15 0 0 1 2 2 3 3 2 4 0 8 4 7 4 6 3 6 1 8 0 11 0 12 2 13 1 14 2 15 0 | 200 100 149 100 149 52 97 52 360 97 5 2 2 2 5 1 1 2 4 5 5 2 2 2 5 |
寻找最近点
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
const int K = 2; //K维：本题是二维
#define ll long long
struct Point{int dim[K];}; //K维数据。本题是二维坐标x=dim[0],y=dim[1]
Point q[N]; //记录输入的n个坐标点
Point t[N]; //存二叉树，用最简单的方法：数组存二叉树
int now; //当前处于第几维，用于cmp()函数的比较
bool cmp(Point a,Point b){return a.dim[now] < b.dim[now];} //第now维数的比较：now为0按照y划分，now为1按照y划分
ll square(int x){return (ll)x*x;}
ll dis(Point a,Point b){ //点a、b距离的平方
return square(a.dim[0]-b.dim[0])+square(a.dim[1]-b.dim[1]);
}
void build(int L,int R,int dep){ //建树
if(L>=R) return; //分到头了
int d = dep % K; //轮转法。dep是当前层的深度，d是当前层的维度
int mid = (L+R) >> 1; //确定中点
now = d;
/* nth_element()函数只是把下标为k的元素放在了正确位置，对其它元素并没有排序，当然k左边元素都小于等于它，
* 右边元素都大于等于它，所以可以利用这个函数快速定位某个元素。
*/
nth_element(t+L,t+mid,t+R,cmp); //找中值
build(L,mid,dep+1); //继续建二叉树的下一层
build(mid+1,R,dep+1);
}
ll ans; //答案：到最近点距离的平方值
void query(int L,int R,int dep,Point p){ //查找点p的最近点
if(L >= R)return;
int mid=(L+R)>>1;
int d = dep % K; //轮转法
ll mindis = dis(t[mid],p); //这棵子树的根到p的最小距离
if(ans == 0) ans = mindis; //赋初值
if(mindis!=0 && ans > mindis) ans = mindis; //需要特判t[mid]和p重合的情况
if(p.dim[d] > t[mid].dim[d]) { //在这个维度，p大于子树的根，接下来查右子树
query(mid+1,R,dep+1,p);
if(ans > square(t[mid].dim[d]-p.dim[d]))
query(L,mid,dep+1,p); //如果以ans为半径的圆与左子树相交，那么左子树也要查
}
else{
query(L,mid,dep+1,p); //在这个维度，p小于子树的根，接下来查左子树
if(ans > square(t[mid].dim[d]-p.dim[d])) //右子树也要查
query(mid+1,R,dep+1,p);
}
}
int main(){
int T; scanf("%d",&T); //测试次数
while(T--){
int n; scanf("%d",&n); //n个点
for(int i=0;i<n;i++)
scanf("%d%d",&(q[i].dim[0]),&(q[i].dim[1])), t[i] = q[i]; //q[],t[]储存点坐标
build(0,n,0); //建树
for(int i=0;i<n;i++){
ans=0;
query(0,n,0,q[i]);
printf("%lld\n",ans);
}
}
return 0;
}
笔记：代码使用的欧氏距离，输出的结果不需要开方处理。轮转法是按照维度交替划分，本节是按照x，y交替划分，用除2取余的结果来交替划分x，y。通过nth_element()函数建立二叉树。mindis储存最近距离，在递归子树的同时查看p点的最小半径是否包含两个子树，如果包含两个子树都递归