记录编号	454256	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]覆盖问题	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.190 s
提交时间	2017-09-28 18:39:17	内存使用	0.47 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=20000+10;
#define inf 1000000 
int n,m,l,r,mid,ans;
struct DATE{int x[M],y[M],num;}date;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void cut(DATE &date,int x1,int y1,int x2,int y2){
    int tot=0;
    for(int i=1;i<=date.num;i++)
        if(date.x[i]<x1||date.x[i]>x2||date.y[i]<y1||date.y[i]>y2){
            tot++;
            date.x[tot]=date.x[i];
            date.y[tot]=date.y[i];
        }
    date.num=tot;
}
inline void solve(DATE &date,int fc){
    int x1=inf,y1=inf,x2=-inf,y2=-inf;
    for(int i=1;i<=date.num;i++){
        x1=min(date.x[i],x1),x2=max(date.x[i],x2);
        y1=min(date.y[i],y1),y2=max(date.y[i],y2);
    }
    if(fc==1)  cut(date,x1,y1,x1+mid,y1+mid);
    if(fc==2)  cut(date,x2-mid,y1,x2,y1+mid);
    if(fc==3)  cut(date,x1,y2-mid,x1+mid,y2);
    if(fc==4)  cut(date,x2-mid,y2-mid,x2,y2);
}
inline bool check(){
    DATE b;
    for(int x=1;x<=4;x++)
        for(int y=1;y<=4;y++){
            b.num=date.num;
            for(int i=1;i<=b.num;i++)
                b.x[i]=date.x[i],b.y[i]=date.y[i];
            solve(b,x);solve(b,y);
            int x1=inf,y1=inf,x2=-inf,y2=-inf;
            for(int i=1;i<=b.num;i++){
                x1=min(b.x[i],x1),x2=max(b.x[i],x2);
                y1=min(b.y[i],y1),y2=max(b.y[i],y2);
            }
            if(x2-x1<=mid&&y2-y1<=mid)return 1;
        }
    return 0;
}
int main(){
    freopen("cover.in","r",stdin);
    freopen("cover.out","w",stdout);
    n=date.num=read();
    for(int i=1;i<=n;++i) date.x[i]=read(),date.y[i]=read();
    l=1,r=M*100;
    while(l<=r){
        mid=l+r>>1;
        if(check()) {ans=mid;r=mid-1;}
        else l=mid+1;
    }printf("%d\n",ans);
    return 0;
}