*【二分】扩散
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
【题意】一个点每过一个单位时间就会向 4 个方向扩散一个距离，如图所示：两个点 a 、b 连通，记作 e(a,b)，当且仅当 a 、b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u、v 都必定存在路径 $e(u,a_0),e(a_0,a_1),…e(a_k,v)$。
给定平面上的 n 个点，问最早什么时候它们形成一个连通块。
【输入格式】
第一行一个数 n ，以下 n 行，每行一个点坐标。
【输出格式】
输出仅一个数，表示最早的时刻所有点形成连通块。
【样例输入】
2
0 0
5 5
【输出】
5
【数据范围与提示】
对于 $20\%$ 的数据，满足 $1 \leq n \leq 5,1 \leq X_i,Y_i \leq 50$；
对于 $100\%$ 的数据，满足 $1 \leq n \leq 50,1 \leq X_i,Y_i \leq 10^9$。
Hint
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n,a[N],b[N],fa[N],s[N];
int findfa(int x){ return (fa[x]==x)?fa[x]: fa[x]=findfa(fa[x]);}
bool check(int x)
{
for(int i=1;i<=n;i++)fa[i]=i,s[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if((abs(a[i]-a[j])+abs(b[i]-b[j])+1)/2<=x)
{
int x=findfa(i),y=findfa(j);
if(x!=y)
{
fa[x]=y;
s[y]+=s[x];
if(s[y]==n)return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
int l=1,r=2e9,ans;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}