KDTree我也只是懂个皮毛而已啦

构建：选取最乱的那一维（方差最大），选取中间点为分界点，然后递归左右空间构建

查找最近点：递归查找，只有左空间或右空间有可能更新答案时才去搜索

例1：BZOJ 1941: [Sdoi2010]Hide and Seek

借鉴了hzw的代码，自己先捣鼓出了曼哈顿距离&无Insert版的KDTree。

构建：两维轮换选，选取中间点为分界点，然后递归左右空间构建，同时护各个空间的Min_xy和Max_xy

查找：递归查找，只有左空间或右空间有可能更新答案时才去搜索

附原题AcCode：

#include <cstdio>
#include <algorithm>

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define down(i, l, r) for(int i=l; i>=r; i--)
#define travel(x) for(edge *p=fir[x]; p; p=p->n)
#define clr(x, c) memset(x, c, sizeof(x))
#define maxn 500009
#define inf 0x3fffffff
#define l(x) Left[x]
#define r(x) Right[x]

using namespace std;
inline int read()
{
	int x=0, f=1; char ch=getchar();
	while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
	while (ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}

int n, F, rt, now, ans, Left[maxn], Right[maxn];
struct node{int x,y;} T[maxn], mn[maxn], mx[maxn], Q;
bool operator < (node a, node b){return (F==0)?(a.x<b.x):(a.y<b.y);}
inline int dis(node &a, node &b){return abs(a.x-b.x)+abs(a.y-b.y);}
inline void Min(node &a, node &b){a.x=min(a.x,b.x); a.y=min(a.y,b.y);}
inline void Max(node &a, node &b){a.x=max(a.x,b.x); a.y=max(a.y,b.y);}

void Build(int l, int r, int now, int &t)
{
	F=now; int mid=(l+r)>>1; t=mid;
	nth_element(T+l, T+mid, T+r+1);
	mn[t]=mx[t]=T[t];
	if (l<mid) Build(l,mid-1,now^1,l(t)), Min(mn[t],mn[l(t)]), Max(mx[t],mx[l(t)]);
	if (mid<r) Build(mid+1,r,now^1,r(t)), Min(mn[t],mn[r(t)]), Max(mx[t],mx[r(t)]);
}
inline int Gmn(int t){return max(Q.x-mx[t].x,0)+max(mn[t].x-Q.x,0)+max(Q.y-mx[t].y,0)+max(mn[t].y-Q.y,0);}
inline int Gmx(int t){return max(abs(Q.x-mn[t].x), abs(Q.x-mx[t].x))+max(abs(Q.y-mn[t].y), abs(Q.y-mx[t].y));}
void Qmx(int t)
{
	now=max(now,dis(T[t],Q));
	int dl=(l(t)?Gmx(l(t)):-inf), dr=(r(t)?Gmx(r(t)):-inf);
	if (dl>dr)
	{
		if (dl>now) Qmx(l(t));
		if (dr>now) Qmx(r(t));
	}
	else
	{
		if (dr>now) Qmx(r(t));
		if (dl>now) Qmx(l(t));
	}
}
void Qmn(int t)
{
	int tmp; if ((tmp=dis(T[t],Q))>0) now=min(now, tmp);
	int dl=(l(t)?Gmn(l(t)):inf), dr=(r(t)?Gmn(r(t)):inf);
	if (dl<dr)
	{
		if (dl<now) Qmn(l(t));
		if (dr<now) Qmn(r(t));
	}
	else
	{
		if (dr<now) Qmn(r(t));
		if (dl<now) Qmn(l(t));
	}
}
inline void Que(int x)
{
	Q=T[x]; int tmp;
	now=-inf, Qmx(rt), tmp=now;
	now=inf, Qmn(rt), tmp-=now;
	ans=min(ans, tmp);
}
int main()
{
	n=read(); rep(i, 1, n) T[i].x=read(), T[i].y=read();
	Build(1,n,0,rt);
	ans=inf; rep(i, 1, n) Que(i);
	printf("%d\n", ans);
	return 0;
}

-update 2015.12.17

例2：BZOJ 2716:[Violet 3]天使玩偶 & BZOJ 2648:SJY摆棋子

例3：BZOJ 4066:简单题

例4：BZOJ 2850:巧克力王国