记录编号	453360	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]覆盖问题	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2017-09-21 12:47:14	内存使用	0.72 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=(ll)1e11+1;
inline ll read(){
    ll s=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9')   k=ch=='-'?-k:k,ch=getchar();
    while(ch>47&&ch<='9')   s=s*10+(ch^48),ch=getchar();
    return s*k;
}
const int N=20020;
struct Point{
    ll x,y;
    friend bool operator<(Point a,Point b){
        return a.x!=b.x?a.x<b.x:a.y<b.y;
    }
    inline void in(){
        x=read(),y=read();
    }
}point[N];
inline bool cmp(Point a,Point b){
    return a.y<b.y;
}
int n;
bool vis[N];
bool ne[4][N];
inline bool dfs(int direction,int step,ll x){
    if(step==4){
        for(int i=1;i<=n;i++)
            if(!vis[i]) return false;
        return true;
    }
    ll r,l,up,down;
    r=up=-inf;
    l=down=inf;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            r=max(r,point[i].x);
            l=min(l,point[i].x);
            up=max(up,point[i].y);
            down=min(down,point[i].y);
        }
    }
    if(up-down<=x&&r-l<=x)  return true;
    else  if(step==3)
        return false;
    else  {
        if(direction==1){
     
            for(int i=1;i<=n;i++){
                if(!vis[i])
                    if(point[i].x-l<=x&&up-point[i].y<=x)
                        vis[i]=ne[step][i]=true;
            }
            for(int i=1;i<=4;i++)
                if(dfs(i,step+1,x))
                    return true;
            for(int i=1;i<=n;i++){
                if(ne[step][i])
                    vis[i]=ne[step][i]=false;
            }
        }else   if(direction==2){
         
            for(int i=1;i<=n;i++){
                if(!vis[i])
                    if(point[i].x-l<=x&&point[i].y-down<=x)
                        vis[i]=ne[step][i]=true;
            }
            for(int i=1;i<=4;i++)
                if(dfs(i,step+1,x))
                    return true;
            for(int i=1;i<=n;i++){
                if(ne[step][i])
                    vis[i]=ne[step][i]=false;
            }
        }else   if(direction==3){
          
            for(int i=1;i<=n;i++){
                if(!vis[i])
                    if(r-point[i].x<=x&&point[i].y-down<=x)
                        vis[i]=ne[step][i]=true;
            }
            for(int i=1;i<=4;i++)
                if(dfs(i,step+1,x))
                    return true;
            for(int i=1;i<=n;i++){
                if(ne[step][i])
                    vis[i]=ne[step][i]=false;
            }
        }else{
            for(int i=1;i<=n;i++){
                if(!vis[i])
                    if(r-point[i].x<=x&&up-point[i].y<=x)
                        vis[i]=ne[step][i]=true;
            }
            for(int i=1;i<=4;i++)
                if(dfs(i,step+1,x))
                    return true;
            for(int i=1;i<=n;i++){
                if(ne[step][i])
                    vis[i]=ne[step][i]=false;
            }
        }
    }
    return false;
}
inline bool Judge(ll x){
    for(int i=1;i<=4;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i,1,x))    
            return true;
    }return false;
}
int main(){
   freopen("cover.in","r",stdin);
    freopen("cover.out","w",stdout);
    //printf("%lld\n",inf);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&point[i].x,&point[i].y);
    sort(point+1,point+n+1);
    for(int i=n;i;i--){
        point[i].x-=point[1].x,point[i].y-=point[1].y;
    }
    ll l=-1,r=2000000100ll;
    while(l<r-1){
        ll mid=l+r>>1;
        if(Judge(mid))  r=mid;
        else    l=mid;
    }
    printf("%ld\n",r);
}