https://www.cnblogs.com/xzxl/p/7237246.html
讲的不错
/*
曼哈顿距离最小生成树 poj 3241 Object Clustering
按照上面的假设我们先考虑y周顺时针45°的情况
dis(i,j)=x[j]-x[i]+y[j]-y[i]=x[j]+y[j]-(x[i]+x[j])
dis取决于x[j]+y[j] 所以排序的关键字就是x+y
然后我们按y-x离散化 然后维护 y-x大于当前点 的点中
x+y最小的点 时间复杂度NlogN
最大生成树的话 不具有对称性 需要往8个方向都搞一遍
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,k,m,num,s[maxn],vl[maxn],idex[maxn],a[maxn],b[maxn],fa[maxn];
struct node{
int x,y,id;
}poi[maxn];
struct edge{
int u,v,t;
}e[maxn*];
int cmp1(const node &A,const node &B){
if(A.x==B.x)return A.y<B.y;
return A.x<B.x;
}
int cmp2(const edge &A,const edge &B){
return A.t<B.t;
}
void Add(int u,int v,int t){
num++;e[num].u=u;
e[num].v=v;e[num].t=t;
}
int Abs(int x){
return x>?x:-x;
}
int Cal(int i,int j){
return Abs(poi[i].x-poi[j].x)+Abs(poi[i].y-poi[j].y);
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Insert(int pos,int val,int id){
while(pos){
if(vl[pos]>val){
vl[pos]=val;idex[pos]=id;
}
pos-=(pos&-pos);
}
}
int Query(int pos){
int res=-,mx=1e9+;
while(pos<=n){
if(mx>vl[pos]){
mx=vl[pos];res=idex[pos];
}
pos+=(pos&-pos);
}
return res;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
scanf("%d%d",&poi[i].x,&poi[i].y);
poi[i].id=i;
}
for(int K=;K<=;K++){
memset(vl,/,sizeof(vl));
memset(idex,-,sizeof(idex));
if(K==||K==)
for(int i=;i<=n;i++)
swap(poi[i].x,poi[i].y);
else if(K==)
for(int i=;i<=n;i++)
poi[i].x=-poi[i].x;
sort(poi+,poi++n,cmp1);
for(int i=;i<=n;i++)// 按照y-x进行离散化
a[i]=b[i]=poi[i].y-poi[i].x;
sort(b+,b++n);
m=unique(b+,b++n)-b-;
for(int i=n;i>=;i--){
int pos=lower_bound(b+,b++m,a[i])-b;
int res=Query(pos);
if(res!=-)
Add(poi[i].id,poi[res].id,Cal(i,res));
Insert(pos,poi[i].x+poi[i].y,i);
}
}
sort(e+,e++num,cmp2);
for(int i=;i<=n;i++)fa[i]=i;
int cnt=n-k;
for(int i=;i<=num;i++){
if(find(e[i].u)==find(e[i].v))continue;
fa[find(e[i].u)]=find(e[i].v);
cnt--;if(cnt==){
printf("%d\n",e[i].t);break;
}
}
return ;
}