| Time Limit: 2000MS | Memory Limit: 131072K | |
| Total Submissions: 1403 | Accepted: 290 |
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
给定平面内一堆点，求曼哈顿距离最小生成树第k大边，
这个结论可以证明如下：假设我们以点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连边。
转自：http://blog.csdn.net/huzecong/article/details/8576908/* ***********************************************
Author :rabbit
Created Time :2014/3/12 13:48:39
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=100100;
struct Point{
int x,y,id;
bool operator < (const Point p) const {
if(x!=p.x)return x<p.x;
return y<p.y;
}
}p[maxn];
struct BIT{
int min_val,pos;
void init(){
min_val=INF;
pos=-1;
}
}bit[maxn<<2];
struct Edge{
int u,v,d;
bool operator < (const Edge p) const {
return d<p.d;
}
}edge[maxn<<2];
int tot,n,F[maxn];
int find(int x){
return F[x]=(F[x]==x?x:find(F[x]));
}
void addedge(int u,int v,int d){
edge[tot].u=u;edge[tot].v=v;edge[tot].d=d;tot++;
}
void update(int i,int val,int pos){
while(i>0){
if(val<bit[i].min_val){
bit[i].min_val=val;
bit[i].pos=pos;
}
i-=i&(-i);
}
}
int ask(int i,int m){
int min_val=INF,pos=-1;
while(i<=m){
if(bit[i].min_val<min_val){
min_val=bit[i].min_val;
pos=bit[i].pos;
}
i+=i&(-i);
}
return pos;
}
int dist(Point a,Point b){
return abs(a.y-b.y)+abs(a.x-b.x);
}
int MHT(int n,Point *p,int k){
int a[maxn],b[maxn];
tot=0;
for(int dir=0;dir<4;dir++){
if(dir==1||dir==3){
for(int i=0;i<n;i++)
swap(p[i].x,p[i].y);
}
if(dir==2){
for(int i=0;i<n;i++)
p[i].x=-p[i].x;
}
sort(p,p+n);
for(int i=0;i<n;i++)
a[i]=b[i]=p[i].y-p[i].x;
sort(b,b+n);
int m=unique(b,b+n)-b;
for(int i=1;i<=m;i++)bit[i].init();
for(int i=n-1;i>=0;i--){
int pos=lower_bound(b,b+m,a[i])-b+1;
int ans=ask(pos,m);
if(ans!=-1)addedge(p[i].id,p[ans].id,dist(p[i],p[ans]));
update(pos,p[i].x+p[i].y,i);
}
}
sort(edge,edge+tot);
for(int i=0;i<n;i++)F[i]=i;
for(int i=0;i<tot;i++){
int u=edge[i].u,v=edge[i].v;
int fa=find(u),fb=find(v);
if(fa!=fb){
k--;
F[fa]=fb;
if(k==0)return edge[i].d;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,k;
while(~scanf("%d%d",&n,&k)){
for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
cout<<MHT(n,p,n-k)<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/21089125