记录编号 |
453360 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HAOI 2007]覆盖问题 |
最终得分 |
100 |
用户昵称 |
Troywar |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.331 s |
提交时间 |
2017-09-21 12:47:14 |
内存使用 |
0.72 MiB |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=(ll)1e11+1;
inline ll read(){
ll s=0,k=1;char ch=getchar();
while(ch<'0'||ch>'9') k=ch=='-'?-k:k,ch=getchar();
while(ch>47&&ch<='9') s=s*10+(ch^48),ch=getchar();
return s*k;
}
const int N=20020;
struct Point{
ll x,y;
friend bool operator<(Point a,Point b){
return a.x!=b.x?a.x<b.x:a.y<b.y;
}
inline void in(){
x=read(),y=read();
}
}point[N];
inline bool cmp(Point a,Point b){
return a.y<b.y;
}
int n;
bool vis[N];
bool ne[4][N];
inline bool dfs(int direction,int step,ll x){
if(step==4){
for(int i=1;i<=n;i++)
if(!vis[i]) return false;
return true;
}
ll r,l,up,down;
r=up=-inf;
l=down=inf;
for(int i=1;i<=n;i++){
if(!vis[i]){
r=max(r,point[i].x);
l=min(l,point[i].x);
up=max(up,point[i].y);
down=min(down,point[i].y);
}
}
if(up-down<=x&&r-l<=x) return true;
else if(step==3)
return false;
else {
if(direction==1){
for(int i=1;i<=n;i++){
if(!vis[i])
if(point[i].x-l<=x&&up-point[i].y<=x)
vis[i]=ne[step][i]=true;
}
for(int i=1;i<=4;i++)
if(dfs(i,step+1,x))
return true;
for(int i=1;i<=n;i++){
if(ne[step][i])
vis[i]=ne[step][i]=false;
}
}else if(direction==2){
for(int i=1;i<=n;i++){
if(!vis[i])
if(point[i].x-l<=x&&point[i].y-down<=x)
vis[i]=ne[step][i]=true;
}
for(int i=1;i<=4;i++)
if(dfs(i,step+1,x))
return true;
for(int i=1;i<=n;i++){
if(ne[step][i])
vis[i]=ne[step][i]=false;
}
}else if(direction==3){
for(int i=1;i<=n;i++){
if(!vis[i])
if(r-point[i].x<=x&&point[i].y-down<=x)
vis[i]=ne[step][i]=true;
}
for(int i=1;i<=4;i++)
if(dfs(i,step+1,x))
return true;
for(int i=1;i<=n;i++){
if(ne[step][i])
vis[i]=ne[step][i]=false;
}
}else{
for(int i=1;i<=n;i++){
if(!vis[i])
if(r-point[i].x<=x&&up-point[i].y<=x)
vis[i]=ne[step][i]=true;
}
for(int i=1;i<=4;i++)
if(dfs(i,step+1,x))
return true;
for(int i=1;i<=n;i++){
if(ne[step][i])
vis[i]=ne[step][i]=false;
}
}
}
return false;
}
inline bool Judge(ll x){
for(int i=1;i<=4;i++){
memset(vis,0,sizeof(vis));
if(dfs(i,1,x))
return true;
}return false;
}
int main(){
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
//printf("%lld\n",inf);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&point[i].x,&point[i].y);
sort(point+1,point+n+1);
for(int i=n;i;i--){
point[i].x-=point[1].x,point[i].y-=point[1].y;
}
ll l=-1,r=2000000100ll;
while(l<r-1){
ll mid=l+r>>1;
if(Judge(mid)) r=mid;
else l=mid;
}
printf("%ld\n",r);
}