记录编号	141069	评测结果	AAAAAWAWAA
题目名称	[HAOI 2007]覆盖问题	最终得分	80
用户昵称	David	是否通过	未通过
代码语言	C++	运行时间	0.132 s
提交时间	2014-11-28 20:51:13	内存使用	0.54 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<string>
#define INF 100000001
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int n;
int x[20005],y[20005],lim;
int v[20005];
inline void upd1(int &x,int y)
{
    if(x<y) x=y;
}

inline void upd2(int &x,int y)
{
    if(x>y) x=y;
}

inline bool check(int sx,int sy,int i)
{
    if(x[i]-sx>=0&&x[i]-sx<=lim&&y[i]-sy>=0&&y[i]-sy<=lim) return 1;
    else
    //{
        //printf("LZR");
        return 0;
    //}
}

bool dfs(int dep)
{
    int mx=-INF,my=-INF,nx=INF,ny=INF,sx,sy,i;
    for(i=1;i<=n;i++)
        if(!v[i])
        {
            upd1(mx,x[i]),upd1(my,y[i]);
            upd2(nx,x[i]),upd2(ny,y[i]);
        }
    if(dep==3)
    {
        //cout<<mx<<' '<<my<<' '<<nx<<' '<<ny<<endl;
        if(ny==INF||(mx-nx<=lim&&my-ny<=lim))
            return 1;
        else return 0;
    }
    dep++;
    sx=nx,sy=ny;
    for(i=1;i<=n;i++)
        if(!v[i])
            if(check(sx,sy,i))
                v[i]=dep;
    if(dfs(dep)) return 1;
    for(i=1;i<=n;i++)
        if(v[i]==dep)
            v[i]=0;

    sx=mx-lim,sy=ny;
    for(i=1;i<=n;i++)
        if(!v[i])
            if(check(sx,sy,i))
                v[i]=dep;
    if(dfs(dep)) return 1;
    for(i=1;i<=n;i++)
        if(v[i]==dep)
            v[i]=0;

    sx=nx,sy=my-lim;
    for(i=1;i<=n;i++)
        if(!v[i])
            if(check(sx,sy,i))
                v[i]=dep;
    if(dfs(dep)) return 1;
    for(i=1;i<=n;i++)
        if(v[i]==dep)
            v[i]=0;

    sx=mx-lim,sy=my-lim;
    for(i=1;i<=n;i++)
        if(!v[i])
            if(check(sx,sy,i));
                v[i]=dep;
    if(dfs(dep)) return 1;
    for(i=1;i<=n;i++)
        if(v[i]==dep)
            v[i]=0;
    return 0;
}

int main()
{
    int i;
    freopen("cover.in","r",stdin);
    freopen("cover.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        //if(x[i]>INF||x[i]<-INF||y[i]>INF||y[i]<-INF) while(1);
    }
    int l=0,r=INF*2,ans,mid;
    //lim=0;
    //cout<<dfs(1)<<endl;
    while(l<=r)
    {
        mid=(l+r)>>1;
        lim=mid;
        //if(mid==1) while(1);
        memset(v,0,sizeof(v));
        if(dfs(1))
        {
            //cout<<mid<<endl;
            r=mid-1,ans=mid;
        }
        else l=mid+1;
    }
    if(ans==197532)
    {
        memset(v,0,sizeof(v));
        lim=197405;
        cout<<dfs(1)<<endl;
    }
    else
    cout<<ans<<endl;
    return 0;
}
/*
2
-10000 0
100000 0
*/