记录编号	317038	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]覆盖问题	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.171 s
提交时间	2016-10-07 16:48:07	内存使用	0.62 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#define me(a,b) memset(a,b,sizeof(a))
#define rep(a,l,r) for(int a=l;a<=r;++a)
#define fcl fclose(stdin);fclose(stdout);return 0;
#define maxn 20005
#define inf 0x3f3f3f3f
using namespace std;
struct Tree{ int x[maxn] , y[maxn] , sum ;}a , b;
int  n , l , r , mid , ans , tot ;
void cut( Tree & t , int x1 , int y1 , int x2 , int y2 )
{
	tot = 0 ;
	rep( i , 1 , t.sum )
	{
		if( t.x[i] < x1 || t.x[i] > x2 || t.y[i] < y1 || t.y[i] > y2 )
		{
			t.x[++tot] = t.x[i];
			t.y[tot] = t.y[i];
		}//在判断的区域外的点 都是没有被删去的  
	} 
	t.sum = tot ;
}
void solve( Tree &t ,int op , int L )
{
	int x1 = inf , y1 = inf , x2 = -inf , y2 = -inf ;
	rep( i , 1 , t.sum )
	{
		x1 = min ( x1 , t.x[i] );
		x2 = max ( x2 , t.x[i] );
		y1 = min ( y1 , t.y[i] );
		y2 = max ( y2 , t.y[i] );
	}
	if( op == 1 )cut( t , x1 , y1 , x1 + L , y1 + L );//左下角 
	if( op == 2 )cut( t , x2 - L , y1 , x2 , y1 + L );// 右下角 
	if( op == 3 )cut( t , x1 , y2 - L , x1 + L , y2 );//左上角 
	if( op == 4 )cut( t , x2 - L , y2 - L , x2  , y2 );//右上角 
}
bool judge(int L)
{
	rep( x , 1 , 4 )
	{
		rep( y , 1 , 4 )
		{
			b = a;
			solve( b , x , L ) , solve( b , y , L );//删去两个正方形的点； 
			int x1 = inf , y1 = inf , x2 = -inf , y2 = -inf ;
			rep( i , 1 , b.sum )
			{
				x1 = min ( x1 , b.x[i] );
				x2 = max ( x2 , b.x[i] );
				y1 = min ( y1 , b.y[i] );
				y2 = max ( y2 , b.y[i] );
			}
			if( x1 + L >= x2 && y1 + L >= y2 )return true; 
		}
	}
	return false;
}
int main()
{
	freopen("cover.in","r",stdin);
	freopen("cover.out","w",stdout);
    scanf( "%d" , &n );
    rep( i , 1 , n )scanf( "%d%d" , &a.x[i] , &a.y[i] );
    a.sum = n ;
    l = 0 , r = inf ;
    while( l <= r )
    {
		mid = ( l + r ) >> 1 ;
		if( judge(mid) )r = mid - 1 ,ans = mid ;
		else l = mid + 1;
	}
	printf( "%d\n" , ans );
}