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;
}