首先可以二分答案，将最优性问题转化为判定性问题。
对于二分到的边长，我们可以把所有的点看成一个大的矩形，这个矩形为包括所有点的最小矩形，那么贪心的想，3个正方形，第一个肯定放在这个矩形其中的一角，然后去掉覆盖的点，然后再求出一个矩形，然后再枚举放在哪一角，去掉之后判断剩下的是否可以由一个正方形覆盖就行了。
反思：没画图，边界算的不对，而且枚举完两个正方形之后要判下是否没有没覆盖的点了。另外提供神样例 4 1 1 -1 -1 1 -1 -1 1答案是2。
/**************************************************************
Problem: 1052
User: BLADEVIL
Language: C++
Result: Accepted
Time:1484 ms
Memory:1280 kb
****************************************************************/
//By BLADEVIL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20010
#define inf (~0U>>1)
using namespace std;
struct rec {
int x,y,flag;
rec(){
x=y=flag=;
}
}a[maxn],b[maxn];
int n;
bool cmp(rec x,rec y) {
return (x.flag<y.flag);
}
void update(rec &MAX,rec &MIN) {
MAX.x=MAX.y=-inf;
MIN.x=MIN.y=inf;
for (int i=;(i<=n)&&(!b[i].flag);i++) {
MAX.x=max(MAX.x,b[i].x);
MIN.x=min(MIN.x,b[i].x);
MAX.y=max(MAX.y,b[i].y);
MIN.y=min(MIN.y,b[i].y);
}
}
void make(int x,int len) {
rec MAX,MIN;
update(MAX,MIN);
//printf("%d %d %d %d\n",MAX.x,MAX.y,MIN.x,MIN.y);
int up,down,left,right;
if (x==) {
up=MAX.y; left=MIN.x;
down=up-len; right=left+len;
}
if (x==) {
up=MIN.y+len; left=MIN.x;
right=left+len; down=MIN.y;
}
if (x==) {
right=MAX.x; left=right-len;
down=MIN.y; up=down+len;
}
if (x==) {
up=MAX.y; down=up-len;
right=MAX.x; left=right-len;
}
//printf("%d %d %d %d %d\n",x,left,right,up,down);
for (int i=;i<=n;i++) if ((b[i].x<=right)&&(b[i].x>=left)&&(b[i].y<=up)&&(b[i].y>=down)) b[i].flag=;
}
bool work(int i,int j,int x) {
memcpy(b,a,sizeof a);
make(i,x);
sort(b+,b++n,cmp);
make(j,x);
sort(b+,b++n,cmp);
rec MAX,MIN;
update(MAX,MIN);
int left=MIN.x,right=MAX.x,up=MAX.y,down=MIN.y;
//printf("%d %d %d %d %d\n",x,left,right,up,down);
if ((left==inf)&&(right==-inf)&&(up==-inf)&&(down==inf)) return ;
if ((MAX.x-MIN.x<=x)&&(MAX.y-MIN.y<=x)) return ; else return ;
}
bool judge(int x) {
for (int i=;i<=;i++)
for (int j=;j<=;j++) if (i!=j) if (work(i,j,x)) return ;
return ;
}
int main() {
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
//printf("%d\n",work(1,2,1)); return 0;
int l=,r=1e9,ans=;
while (l<=r) {
//printf("%d %d\n",l,r);
int mid=l+r>>;
if (judge(mid)) ans=mid,r=mid-; else l=mid+;
}
printf("%d\n",ans);
return ;
}