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+20, M = 4e4+10, mod = 1e9+7, inf = 0x3f3f3f3f; typedef long long ll;struct ss{int u,v,w;bool operator < (const ss &b) const{return w < b.w;} }e[N * 4]; int tot = 0 ,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 = -1, 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 >= 1; i -= i&(-i)) if(mi[i] > c) mi[i] = c, pos[i] = p; }int haxi(int x) {return lower_bound(san + 1, san + cnt + 1, x) - san;} int dis(int i,int j) {return abs(x[i] - x[j]) + abs(y[i] - y[j]); } void Manst() {tot = 0;for(int dir = 0; dir < 4; ++dir) {if(dir == 1 || dir == 3)for(int i = 1; i <= n; ++i) swap(x[i],y[i]);elsefor(int i = 1; i <= n; ++i) x[i] = -x[i];for(int i = 1; i <= n; ++i) id[i] = i;sort(id + 1, id + n + 1, cmp);cnt = 0;for(int i = 1; i <= n; ++i) san[++cnt] = y[i] - x[i];sort(san + 1, san + cnt + 1);cnt = unique(san + 1, san + cnt + 1) - san - 1;for(int i = 1; i <= n; ++i) mi[i] = inf , pos[i] = -1;for(int i = n; i >= 1; --i) {int u = haxi(y[id[i]] - x[id[i]]);int v = query(u);if(v != -1) 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=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);Manst();sort(e + 1, e+ tot + 1);for(int i = 1; i <= n; ++i) fa[i] = i;k = n - k;for(int i = 1; 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 == 0) {printf("%d\n",c);break;}}}} }
