Description
We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of object i and object j is defined by dij = |ai - aj| + |bi - bj|, and then we say i is dij resemble to j. Now we want to find the minimum value of X, so that we can classify the N objects into K (K < N) groups, and in each group, one object is at most X resemble to another object in the same group, i.e, for every object i, if i is not the only member of the group, then there exists one object j (i ≠ j) in the same group that satisfies dij ≤ X
Input
The first line contains two integers N and K. The following N lines each contain two integers a and b, which describe a object.
Output
A single line contains the minimum X.
Sample Input
6 2
1 2
2 3
2 2
3 4
4 3
3 1
Sample Output
2
整个题：就是求manhattan最小生成树
曼哈顿距离最小生成树问题可以简述如下：
给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。
朴素的算法可以用O(N2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O(N2)条，所以Kruskal的复杂度变成了O(N2logN)。
但是事实上，真正有用的边远没有O(N2)条。我们考虑每个点会和其他一些什么样的点连边。可以得出这样一个结论，以一个点为原点建立直角坐标系，在每45度内只会向距离该点最近的一个点连边。
这个结论可以证明如下：假设我们以点A为原点建系，考虑在y轴向右45度区域内的任意两点B(x1,y1)和C(x2,y2)，不妨设|AB|≤|AC|（这里的距离为曼哈顿距离），如下图：
|AB|=x1+y1，|AC|=x2+y2，|BC|=|x1-x2|+|y1-y2|。而由于B和C都在y轴向右45度的区域内，有y-x>0且x>0。下面我们分情况讨论：
1. x1>x2且y1>y2。这与|AB|≤|AC|矛盾；
2. x1≤x2且y1>y2。此时|BC|=x2-x1+y1-y2，|AC|-|BC|=x2+y2-x2+x1-y1+y2=x1-y1+2*y2。由前面各种关系可得y1>y2>x2>x1。假设|AC|<|BC|即y1>2*y2+x1，那么|AB|=x1+y1>2*x1+2*y2，|AC|=x2+y2<2*y2<|AB|与前提矛盾，故|AC|≥|BC|；
3. x1>x2且y1≤y2。与2同理；
4. x1≤x2且y1≤y2。此时显然有|AB|+|BC|=|AC|，即有|AC|>|BC|。
综上有|AC|≥|BC|，也即在这个区域内只需选择距离A最近的点向A连边。
这种连边方式可以保证边数是O(N)的，那么如果能高效处理出这些边，就可以用Kruskal在O(NlogN)的时间内解决问题。下面我们就考虑怎样高效处理边。
我们只需考虑在一块区域内的点，其他区域内的点可以通过坐标变换“移动”到这个区域内。为了方便处理，我们考虑在y轴向右45度的区域。在某个点A(x0,y0)的这个区域内的点B(x1,y1)满足x1≥x0且y1-x1>y0-x0。这里对于边界我们只取一边，但是操作中两边都取也无所谓。那么|AB|=y1-y0+x1-x0=(x1+y1)-(x0+y0)。在A的区域内距离A最近的点也即满足条件的点中x+y最小的点。因此我们可以将所有点按x坐标排序，再按y-x离散，用线段树或者树状数组维护大于当前点的y-x的最小的x+y对应的点。时间复杂度O(NlogN)。
至于坐标变换，一个比较好处理的方法是第一次直接做；第二次沿直线y=x翻转，即交换x和y坐标；第三次沿直线x=0翻转，即将x坐标取相反数；第四次再沿直线y=x翻转。注意只需要做4次，因为边是双向的。
至此，整个问题就可以在O(NlogN)的复杂度内解决了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include<vector>
#include <algorithm>
using namespace std;
const int N = 1e4+, M = 4e4+, mod = 1e9+, inf = 0x3f3f3f3f;
typedef long long ll; struct ss{
int u,v,w;
bool operator < (const ss &b) const
{
return w < b.w;
}
}e[N * ];
int tot = ,id[N] , mi[N] , pos[N] , x[N], cnt , y[N], san[N], fa[N], n ,k;
bool cmp(int i,int j)
{
if(x[i] != x[j]) return x[i] < x[j];
else return y[i] < y[j];
}
void add(int u,int v,int w) {
++tot;
e[tot].u = u, e[tot].v = v, e[tot].w = w;
}
int query(int x) {
int ret = -, ans = inf;
for(int i = x; i <= cnt; i += i&(-i)) {
if(mi[i] < ans) ans = mi[i] , ret = pos[i];
}
return ret;
}
void update(int x, int c, int p) {
for(int i = x; i >= ; i -= i&(-i)) if(mi[i] > c) mi[i] = c, pos[i] = p;
} int haxi(int x) {return lower_bound(san + , san + cnt + , x) - san;}
int dis(int i,int j)
{
return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
void Manst() {
tot = ;
for(int dir = ; dir < ; ++dir) {
if(dir == || dir == )
for(int i = ; i <= n; ++i) swap(x[i],y[i]);
else
for(int i = ; i <= n; ++i) x[i] = -x[i];
for(int i = ; i <= n; ++i) id[i] = i;
sort(id + , id + n + , cmp);
cnt = ;
for(int i = ; i <= n; ++i) san[++cnt] = y[i] - x[i];
sort(san + , san + cnt + );
cnt = unique(san + , san + cnt + ) - san - ;
for(int i = ; i <= n; ++i) mi[i] = inf , pos[i] = -;
for(int i = n; i >= ; --i) {
int u = haxi(y[id[i]] - x[id[i]]);
int v = query(u);
if(v != -) add(id[i], v, dis(id[i], v));
update(u, x[id[i]] + y[id[i]], id[i]);
}
}
} int finds(int x) {return x==fa[x]?x:fa[x]=finds(fa[x]);} int main()
{
while(~scanf("%d%d",&n,&k)) { for(int i=;i<=n;i++) scanf("%d%d",&x[i],&y[i]); Manst();
sort(e + , e+ tot + );
for(int i = ; i <= n; ++i) fa[i] = i;
k = n - k;
for(int i = ; i <= tot; ++i)
{
int u = e[i].u, v = e[i].v, c = e[i].w;
if(finds(u) != finds(v)) {
--k;
fa[finds(u)] = finds(v);
if(k == ) {
printf("%d\n",c);
break;
}
}
}
}
}