https://www.saowen.com/a/b932190a4724dc877aeaa3c8e8dfd5abacb402e661d9472f06d1bf0590cd8ee6

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MN 20005
#define INF 0x3FFFFFFF
using namespace std;
struct node{int x,y;}a[MN];
int b[MN];
int bin,n,L,R;

inline int read()
{
    int n=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
    return n*f;
}

bool cov(int len)
{
    if (!bin) return true;
    register int i,lm,rm,dm,um;
    lm=dm=INF; rm=um=-INF;
    for (i=1;i<=bin;++i)
        lm=min(lm,a[b[i]].x),rm=max(rm,a[b[i]].x),
        dm=min(dm,a[b[i]].y),um=max(um,a[b[i]].y);
    for (i=1;i<=bin;++i)
        if (!(a[b[i]].x<=lm+len&&a[b[i]].y<=dm+len
            ||a[b[i]].x>=rm-len&&a[b[i]].y>=um-len)) break;
    if (i>bin) return true;
    for (i=1;i<=bin;++i)
        if (!(a[b[i]].x<=lm+len&&a[b[i]].y>=um-len
            ||a[b[i]].x>=rm-len&&a[b[i]].y<=dm+len)) break;
    if (i>bin) return true;
    return false;
}

void del(int lm,int dm,int rm,int um)
{
    register int i;
    for (bin=0,i=1;i<=n;++i)
        if (a[i].x<lm||a[i].x>rm||a[i].y<dm||a[i].y>um) b[++bin]=i;
}

int main()
{
    register int i,lm,rm,dm,um;
    lm=dm=INF; rm=um=-INF;
    n=read();
    for (i=1;i<=n;++i)
        a[i].x=read(),a[i].y=read(),
        lm=min(lm,a[i].x),rm=max(rm,a[i].x),
        dm=min(dm,a[i].y),um=max(um,a[i].y);
    L=0; R=max(um-dm,rm-lm);
    while (L<R)
    {
        int mid=L+R>>1;
        for (i=1;i<=4;++i)
        {
                 if (i==1) del(lm,dm,lm+mid,dm+mid);
            else if (i==2) del(lm,um-mid,lm+mid,um);
            else if (i==3) del(rm-mid,dm,rm,dm+mid);
            else if (i==4) del(rm-mid,um-mid,rm,um);
            if (cov(mid)) break;
        }
        if (i<=4) R=mid; else L=mid+1;
    }
    printf("%d",L);
}