记录编号	317315	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]覆盖问题	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	0.632 s
提交时间	2016-10-07 20:48:30	内存使用	0.46 MiB

/*
  Name: 覆盖问题 
  Author: LOSER?
  Date: 07/10/16 17:48
  Description:
		只能说恶心 ! ! ! 考场上想出了二分可是去没有想出合适的 Judge 方式所以....
		说一下 Judge 的方式
		首先找出用一个矩形覆盖所有点的方式 那么这个矩形的一个角必须被覆盖
		接下来不断递归即可 
		注意 ::	 左区间为 1  
*/
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 20010
#define inf 0x7f7f7f7f
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)
int n,cnt;
struct MAP{
	int x,y;	
}a[maxn];
bool flag[maxn];
bool Judge(int mid){
	int up=-inf,l=inf,r=-inf,down=inf;
	bool Check=0;
	for(int i=1;i<=n;i++){
		if(!flag[i]){
			Check=1;
		}
	}if(!Check && cnt<=3){return true;}
	if(Check && cnt>=3){return false;}
	for(int i=1;i<=n;i++){
		if(flag[i])continue;
		up=MAX(up,a[i].y); down=MIN(down,a[i].y);
		l=MIN(l,a[i].x); r=MAX(r,a[i].x);
	}
	for(int i=1;i<=n;i++){
		if(flag[i])continue;
		if((a[i].x>=l) && (a[i].x<=l+mid) && (a[i].y<=up) && (a[i].y>=up-mid))flag[i]=1;
	}	cnt++;
	if( Judge(mid) )return true;
	else {
		for(int i=1;i<=n;i++){
			if(a[i].x>=l && a[i].x<=l+mid && a[i].y<=up && a[i].y>=up-mid)flag[i]=0;	
		}	cnt--;
	}
	for(int i=1;i<=n;i++){
		if(flag[i])continue;
		if(a[i].x>=l && a[i].x<=l+mid && a[i].y>=down && a[i].y<=down+mid){
			flag[i]=1;
		}	
	}	cnt++;
	if(Judge(mid))return true;
	else{
		for(int i=1;i<=n;i++){
			if(a[i].x>=l && a[i].x<=l+mid && a[i].y>=down && a[i].y<=down+mid)flag[i]=0;	
		}	cnt--;	
	}
	for(int i=1;i<=n;i++){
		if(flag[i])continue;
		if(a[i].x<=r && a[i].x>=r-mid && a[i].y<=up && a[i].y>=up-mid)flag[i]=1;	
	}	cnt++;
	if(Judge(mid))return true;
	else{
		for(int i=1;i<=n;i++){
			if(a[i].x<=r && a[i].x>=r-mid && a[i].y<=up && a[i].y>=up-mid)flag[i]=0;	
		}	cnt--;
	}
	for(int i=1;i<=n;i++){
		if(flag[i])continue;
		if(a[i].x<=r && a[i].x>=r+mid && a[i].y>=down && a[i].y<=down+mid)flag[i]=1;	
	}	cnt++;
	if(Judge(mid)) return true;
	else{
		for(int i=1;i<=n;i++){
			if(a[i].x<=r && a[i].x>=r+mid && a[i].y>=down && a[i].y<=down+mid)flag[i]=0;	
		}	cnt--;		
	}
	return false;
}
int main(){
	freopen("cover.in","r",stdin); freopen("cover.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	int l=1,r=2100000000;
#define mid ((l+r)>>1)
	while(l<=r){
		memset(flag,0,sizeof(flag)); cnt=0;
		if(Judge(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
	getchar(); getchar();
	return 0;	
}
/*
1
6 8
*/