记录编号	316986	评测结果	AAWWWAWAAA
题目名称	[HAOI 2007]覆盖问题	最终得分	60
用户昵称	Hzoi_chairman	是否通过	未通过
代码语言	C++	运行时间	0.045 s
提交时间	2016-10-07 16:05:17	内存使用	0.47 MiB

/*
  Name: 覆盖问题
  Copyright: 
  Author: chairman
  Date: 07/10/16 15:58
  Description: 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 20100
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
struct node
{
	int x,y;
}a[maxn];
bool com(const node & a,const node & b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int up[5],down[5],le[5],ri[5],mid;
bool check(int x,int i)
{
	if(a[i].x<le[x]||a[i].x>ri[x])return 0;
	if(a[i].y<=up[x]&&a[i].y>=down[x])return 1;
	if(a[i].y>up[x])
	{
		if(a[i].y-down[x]<=mid)
		{
			up[x]=a[i].y;
			return 1;
		}
		else return 0;
	}
	if(a[i].y<down[x])
	{
		if(up[x]-a[i].y<=mid)
		{
			down[x]=a[i].y;
			return 1;
		}
		else return 0;
	}
	return 1;
}
int main()
{
	freopen("cover.in","r",stdin);
	freopen("cover.out","w",stdout);	
	int n=read(),maxx=0,mixx=0x7f7f7f7f,mayy=0,miyy=0x7f7f7f7f;
	for(int i=1;i<=n;i++)
	{
		a[i].x=read();a[i].y=read();
		maxx=max(maxx,a[i].x);
		mixx=min(mixx,a[i].x);
		mayy=max(mayy,a[i].y);
		miyy=min(miyy,a[i].y);
	}
	sort(a+1,a+1+n,com);
	int l=1,r=max(maxx-mixx,mayy-miyy);
	while(l<=r)
	{
		mid=(l+r)>>1;
		int cnt=1;
		memset(up,0,sizeof up);
		memset(down,0,sizeof down);
		memset(le,0,sizeof le);
		memset(ri,0,sizeof ri);
		up[1]=a[1].y;down[1]=a[1].y;
		le[1]=a[1].x;ri[1]=a[1].x+mid;
		bool f=0;
		for(int i=2;i<=n;i++)
		{
			if(!check(1,i))//不在第1块的覆盖范围 
			{
				if(cnt<2)//使用第2块 
				{
					cnt=2;
					up[2]=a[i].y;down[2]=a[i].y;
					le[2]=a[i].x;ri[2]=a[i].x+mid;
					continue; 
				}
				if(cnt>=2)
				{
					if(!check(2,i))//不在第2块的覆盖范围 
					{
						if(cnt<3)//使用第3块 
						{
							cnt=3;
							up[3]=a[i].y;down[3]=a[i].y;
							le[3]=a[i].x;ri[3]=a[i].x+mid;
							continue;
						}
						if(cnt==3&&!check(3,i))//不在第3块的覆盖范围 
						{
							f=1;break;
						}
					}
				}
			}
		}
		if(f)l=mid+1;
		else r=mid-1;
	}
	write(r+1);//while(1);
//	system("pause");
	fclose(stdin);
	fclose(stdout);
}