K-D树实际上是一棵高维二叉搜索树，与普通二叉搜索树不同的是，树中存储的是一些K维数据
普通的二叉搜索树是一维的，当推广到K维后，就是我们的K-D树了
在K-D树中跟二叉搜索树差不多，也是将一个K维的数据与根节点进行比较，然后划分的
这里的比较不是整体的比较，而是选择其中一个维度来进行比较
在K-D树进行划分时，可以每次选择方差最大的属性来划分数据到左右子树
在K-D树的划分中，这个轴的选取很关键，要保证划分后的左右子树尽量平衡
那么很显然选取这个属性的值对应数组的中位数作为pivot
然后是查找了，最邻近查找的算法描述如下
（）将查询数据Q从根节点开始，按照Q与各个节点的比较结果向下遍历，直到到达叶子节点为止。 到达叶子节点时，计算Q与叶子节点上保存的所有数据之间的距离，记录最小距离对应的数据点， 假设当前最邻近点为p_cur，最小距离记为d_cur （）进行回溯操作，该操作的目的是找离Q更近的数据点，即在未访问过的分支里，是否还有离Q更近的点 它们的距离小于d_cur
然后一道模板题，BZOJ1941，给出平面上n个点，求距离每个点最大距离减最小距离(不算自己)的最小值
枚举每个点找最近点，最远点更新答案
敲的好累啊！！
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=;
const int mod=;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,F,rt,ans=INF;
int x[],y[];
struct P
{
int d[],mn[],mx[],l,r;
int& operator[](int x)
{
return d[x];
}
friend bool operator<(P a,P b)
{
return a[F]<b[F];
}
friend int dis(P a,P b)
{
return abs(a[]-b[])+abs(a[]-b[]);
}
}p[];
struct kdtree
{
P t[],T;
int ans;
void update(int k)
{
int l=t[k].l,r=t[k].r;
for(int i=;i<;i++)
{
t[k].mn[i]=t[k].mx[i]=t[k][i];
if(l) t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);
if(r) t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);
if(l) t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
if(r) t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
}
}
int build(int l,int r,int now)
{
F=now;
int mid=(l+r)>>;
nth_element(p+l,p+mid,p+r+);
t[mid]=p[mid];
for(int i=;i<;i++)
t[mid].mn[i]=t[mid].mx[i]=t[mid][i];
if(l<mid) t[mid].l=build(l,mid-,now^);
if(r>mid) t[mid].r=build(mid+,r,now^);
update(mid);
return mid;
}
int getmn(P a)
{
int ans=;
for(int i=;i<;i++)
{
ans+=max(T[i]-a.mx[i],);
ans+=max(a.mn[i]-T[i],);
}
return ans;
}
int getmx(P a)
{
int ans=;
for(int i=;i<;i++)
ans+=max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i]));
return ans;
}
void querymx(int k)
{
ans=max(ans,dis(t[k],T));
int l=t[k].l,r=t[k].r,dl=-INF,dr=-INF;
if(l) dl=getmx(t[l]);if(r) dr=getmx(t[r]);
if(dl>dr)
{
if(dl>ans)querymx(l);
if(dr>ans)querymx(r);
}
else
{
if(dr>ans)querymx(r);
if(dl>ans)querymx(l);
}
}
void querymn(int k)
{
int tmp=dis(t[k],T);
if(tmp)ans=min(ans,tmp);
int l=t[k].l,r=t[k].r,dl=INF,dr=INF;
if(l)dl=getmn(t[l]);if(r)dr=getmn(t[r]);
if(dl<dr)
{
if(dl<ans)querymn(l);
if(dr<ans)querymn(r);
}
else
{
if(dr<ans)querymn(r);
if(dl<ans)querymn(l);
}
}
int query(int f,int x,int y)
{
T[]=x;T[]=y;
if(f==)ans=INF,querymn(rt);
else ans=-INF,querymx(rt);
return ans;
}
}kdtree;
int main()
{
n=read();
for(int i=;i<=n;i++)
{
x[i]=read(),y[i]=read();
p[i][]=x[i];p[i][]=y[i];
}
rt=kdtree.build(,n,);
for(int i=;i<=n;i++)
{
int mn=kdtree.query(,x[i],y[i]),mx=kdtree.query(,x[i],y[i]);
ans=min(ans,mx-mn);
}
printf("%d\n",ans);
return ;
}