注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1052][HAOI2007]覆盖问题  

2014-05-08 15:35:24|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@[BZOJ1052][HAOI2007]覆盖问题

看出来是二分答案,但是不知道要怎么check....

多亏zky神犇告诉我Orz

利用了三个正方形的特性,一定是在角上

如果是超过四个正方形就不成立了

如果有神犇会比较好的四个正方形的解决办法请告诉俺~

#include<cstdio>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 20000+1;
const int _MAX = 2100000000;
int n,m,listx[N],listy[N];
int lx,rx,ly,ry;
bool v[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+'){cc=getchar();fh=1;}
if(cc=='-'){cc=getchar();fh=-1;}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct Point{
int x,y;
Point(){}
Point(int xx,int yy):x(xx),y(yy){}
}list[N];
void select(Point l,Point r){
lx=ly=_MAX;
rx=ry=-_MAX;
for(int i=1;i<=n;i++)
if((l.x<=list[i].x&&list[i].x<=r.x)&&(l.y<=list[i].y&&list[i].y<=r.y)){
v[i]=1;
}else if(!v[i]){
int a=list[i].x,b=list[i].y;
if(lx>a)lx=a;
if(ly>b)ly=b;
if(rx<a)rx=a;
if(ry<b)ry=b;
}
}
bool check(int L,int left){
if(lx==_MAX) return 1;
if(left){
int slx=lx,srx=rx,sly=ly,sry=ry,a;
bool ok,save[N];
for(int i=1;i<=n;i++)save[i]=v[i];
//7
select(Point(lx,ly),Point(lx+L,ly+L));
ok=check(L,left-1);
lx=slx;rx=srx;
ly=sly;ry=sry;
for(int i=1;i<=n;i++)v[i]=save[i];
if(ok) return 1;
if(left==1) return ok;
//9
select(Point(rx-L,ly),Point(rx,ly+L));
ok=check(L,left-1);
lx=slx;rx=srx;
ly=sly;ry=sry;
for(int i=1;i<=n;i++)v[i]=save[i];
if(ok) return 1;
//1
select(Point(lx,rx-L),Point(lx+L,rx));
ok=check(L,left-1);
lx=slx;rx=srx;
ly=sly;ry=sry;
for(int i=1;i<=n;i++)v[i]=save[i];
if(ok) return 1;
//3
select(Point(rx-L,ry-L),Point(rx,ry));
ok=check(L,left-1);
lx=slx;rx=srx;
ly=sly;ry=sry;
for(int i=1;i<=n;i++)v[i]=save[i];
if(ok) return 1;
}
return 0;
}
int main(){
//freopen("input.txt","r",stdin);
int i,j,a,b;
lx=ly=_MAX;
rx=ry=-_MAX;
n=scan();
for(i=1;i<=n;i++){
a=scan();b=scan();
list[i]=Point(a,b);
if(lx>a)lx=a;
if(ly>b)ly=b;
if(rx<a)rx=a;
if(ry<b)ry=b;
}
int L=1,R=max(rx-lx,ry-ly);
while(L<R){
int mid=(L+R)/2;
if(check(mid,3))R=mid;
else L=mid+1;
}
printf("%d\n",L);
return 0;
}


  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017