题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。

输入输出格式

输入格式：

第一行一个数n，以下n行，每行一个点坐标。

【数据规模】

对于20%的数据，满足1≤N≤5; 1≤X[i],Y[i]≤50;

对于100%的数据，满足1≤N≤50; 1≤X[i],Y[i]≤10^9。

输出格式：

一个数，表示最早的时刻所有点形成连通块。

输入输出样例

2

0 0

5 5

5

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct edge{

     int x,y;

     int d;

 }e[mxn*mxn];

 int mct=;

 int cmp(edge a,edge b){

     return a.d<b.d;

 }

 struct point{

     int x,y;

 }a[mxn];

 int fa[mxn];

 int find(int x){

     if(fa[x]==x)return x;

     return fa[x]=find(fa[x]);

 }

 int dist(int x,int y){

     return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);

 }

 //int mp[mxn][mxn];

 int n,ans=;

 void solve(){

     int i,j;

     for(i=;i<=n;i++)fa[i]=i;

     int num=;

     for(i=;i<=mct;i++){

         int x=e[i].x;

         int y=e[i].y;

         x=find(x);y=find(y);

         if(x!=y){

             ans=max(ans,e[i].d);

             num++;

             fa[x]=y;

         }

         if(num==n)break;

     }

     return;

 }

 int main(){

     int i,j;

     n=read();

     for(i=;i<=n;i++){

         a[i].x=read();

         a[i].y=read();

     }

     for(i=;i<n;i++)

      for(j=i+;j<=n;j++){

          e[++mct].x=i;e[mct].y=j;

          e[mct].d=dist(i,j);

      }

     sort(e+,e+mct+,cmp);

     //

     solve();

     printf("%d\n",(ans+)/);

     return ;

 }