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
又是一道曼哈顿距离最小生成树。。。
code：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 100005 7 #define inf 1061109567 8 using namespace std; 9 char ch; 10 bool ok; 11 void read(int &x){ 12 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 13 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 14 if (ok) x=-x; 15 } 16 struct Point{ 17 int x,y,d,id; 18 }point[maxn],tmp[maxn]; 19 bool cmp1(Point a,Point b){ 20 if (a.x!=b.x) return a.x>b.x; 21 return a.y>b.y; 22 } 23 int calc(Point a,Point b){return abs(a.x-b.x)+abs(a.y-b.y);} 24 int n,m,k,ans; 25 struct DATA{ 26 int val,pos; 27 void init(){val=inf,pos=-1;} 28 void update(DATA b){if (val>b.val) val=b.val,pos=b.pos;} 29 }; 30 int d[maxn],cntd; 31 struct bit{ 32 #define lowbit(x) ((x)&(-(x))) 33 DATA node[maxn]; 34 void init(){for (int i=1;i<=cntd;i++) node[i].init();} 35 void insert(int x,DATA p){for (int i=cntd-x+1;i<=cntd;i+=lowbit(i)) node[i].update(p);} 36 int query(int x){ 37 DATA ans; ans.init(); 38 for (int i=cntd-x+1;i;i-=lowbit(i)) ans.update(node[i]); 39 return ans.pos; 40 } 41 }T; 42 struct Edge{ 43 int u,v,c; 44 }edge[maxn<<2]; 45 bool cmp2(Edge a,Edge b){return a.c<b.c;} 46 void prepare(){ 47 for (int i=1;i<=n;i++) d[i]=point[i].d=point[i].y-point[i].x; 48 sort(d+1,d+n+1),cntd=unique(d+1,d+n+1)-d-1; 49 for (int i=1;i<=n;i++) point[i].d=lower_bound(d+1,d+cntd+1,point[i].d)-d; 50 sort(point+1,point+n+1,cmp1),T.init(); 51 for (int i=1;i<=n;i++){ 52 int u=point[i].id,v=T.query(point[i].d); 53 if (v!=-1) edge[++m]=(Edge){u,v,calc(tmp[u],tmp[v])}; 54 T.insert(point[i].d,(DATA){point[i].x+point[i].y,u}); 55 } 56 } 57 int fa[maxn]; 58 int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);} 59 int main(){ 60 read(n),read(k); 61 for (int i=1;i<=n;i++) read(point[i].x),read(point[i].y),point[i].id=i; 62 for (int i=1;i<=n;i++) tmp[i]=point[i]; prepare(); 63 for (int i=1;i<=n;i++) point[i].x=tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare(); 64 for (int i=1;i<=n;i++) point[i].x=-tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare(); 65 for (int i=1;i<=n;i++) point[i].x=tmp[i].x,point[i].y=-tmp[i].y,point[i].id=i; prepare(); 66 sort(edge+1,edge+m+1,cmp2); 67 for (int i=1;i<=n;i++) fa[i]=i; 68 for (int i=1,cnt=n;i<=m&&cnt>k;i++) if (find(edge[i].u)!=find(edge[i].v)) 69 cnt--,ans=max(ans,edge[i].c),fa[find(edge[i].u)]=find(edge[i].v); 70 printf("%d ",ans); 71 return 0; 72 }