并查集+二分答案
//我感觉连通性往往跟并查集有关,然后我们可以试着给定答案,看看答案是否满足
//这道题有点曼哈顿距离给我的感觉(因为它只能走四个方位,不很想曼哈顿距离不)
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 55,M = 1e9;
int p[N];
PII w[N];
int n;
int find(int x){
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
bool check(int x){
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(abs(w[i].x-w[j].x)+abs(w[i].y-w[j].y)<=2*x&&find(i)!=find(j)){
p[find(i)]=find(j);
}
}
}
int cnt=0;
for(int i=1;i<=n;i++){
if(i==find(i))cnt++;
}
return cnt==1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i].x>>w[i].y;
int l=-1,r=M+1;
//我们二分时间
while(l+1!=r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid;
}
cout<<r;
return 0;
}