温馨提示：这题跟二分一点儿关系都没有！

难度： 黄

算法标签： 最小生成树

一道最小生成树的题。

记两个点的距离为它们形成连通块的最早时间，每两个点连一条边，然后直接跑最小生成树即可。

本题数据极水，任何最小生成树算法均可以通过。

贴出代码：（ Kruskal ）

#include<bits/stdc++.h>
using namespace std;
int n,m=0,x[55],y[55],fa[55],t=0;
struct edge{
	int l,r,w;
}e[3333];
int dis(int a,int b){
	return int(abs(x[a]-x[b])+abs(y[a]-y[b])+1)/2;
}
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int getfa(int a){
	if(fa[a]==a) return a;
	return fa[a]=getfa(fa[a]);
}
void un(int a,int b){
	fa[fa[b]]=fa[a];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j){
				e[++m].l=i,e[m].r=j;
				e[m].w=dis(i,j);
			}	
		}
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		if(getfa(e[i].l)!=getfa(e[i].r)){
			t++;
			un(e[i].l,e[i].r);
			if(t==n-1){
				printf("%d",e[i].w);
				return 0;
			}
		}
	}
}