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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1052】【HAOI2007】【覆盖问题】  

2014-03-17 15:58:42|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   给出一些点,用三个边长均为L的与坐标轴平行的正方形覆盖这些点,求L的最小值
   我们首先可以得到左下角的点和右上角的点和左上角的点和右上角的点(就是覆盖这些点的一个矩阵的四个角),一个最优解很显然就是第一个正方形以这四个中一个作为边界,那么咱们可以来二分答案L,那么咱们就可以去掉一些点,然后咱们的问题就是对于剩余的点咱们求出最小的正方形即可,看它是否小于等于L,显然这个扫一遍就可以了(求出最远的),复杂度O(NlogL)。
   写的很恶心...四种情况由于对称就写一种,然后其他的复制这一种
==============================

program bzoj1052;
const maxn=20010;
var maxx,minx,maxy,miny:int64;
x,y,st:array[0..maxn]of int64;
v:array[0..maxn]of boolean;
n:longint;

function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;

function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;

function check(l,dep:longint):boolean;
var maxx,minx,maxy,miny:int64;
i,ll:longint;
begin
maxx:=-maxlongint;maxy:=maxx;
minx:=maxlongint;miny:=minx;
for i:=1 to n do
if not v[i] then
begin
maxx:=max(maxx,x[i]);maxy:=max(maxy,y[i]);
minx:=min(minx,x[i]);miny:=min(miny,y[i]);
end;
if dep=3 then
if l>=max(maxx-minx,maxy-miny) then exit(true)
else exit(false);
ll:=st[0];
for i:=1 to n do
if (not v[i])and(x[i]<=minx+l)and(y[i]<=miny+l) then
begin
v[i]:=true;
inc(st[0]);
st[st[0]]:=i;
end;
if check(l,dep+1) then exit(true);
for i:=ll+1 to st[0] do
v[st[i]]:=false;
st[0]:=ll;
for i:=1 to n do
if (not v[i])and(x[i]>=maxx-l)and(y[i]<=miny+l) then
begin
v[i]:=true;
inc(st[0]);
st[st[0]]:=i;
end;
if check(l,dep+1) then exit(true);
for i:=ll+1 to st[0] do
v[st[i]]:=false;
st[0]:=ll;
for i:=1 to n do
if (not v[i])and(x[i]>=maxx-l)and(y[i]>=maxy-l) then
begin
v[i]:=true;
inc(st[0]);
st[st[0]]:=i;
end;
if check(l,dep+1) then exit(true);
for i:=ll+1 to st[0] do
v[st[i]]:=false;
st[0]:=ll;
for i:=1 to n do
if (not v[i])and(x[i]<=minx+l)and(y[i]>=maxy-l) then
begin
v[i]:=true;
inc(st[0]);
st[st[0]]:=i;
end;
if check(l,dep+1) then exit(true);
for i:=ll+1 to st[0] do
v[st[i]]:=false;
st[0]:=ll;
exit(false);
end;

procedure init;
var i,l,r,mid:longint;
begin
read(n);
maxx:=-maxlongint;maxy:=maxx;
minx:=maxlongint;miny:=minx;
for i:=1 to n do
begin
read(x[i],y[i]);
maxx:=max(maxx,x[i]);maxy:=max(maxy,y[i]);
minx:=min(minx,x[i]);miny:=min(miny,y[i]);
end;
l:=0;r:=maxx-minx;
if r<maxy-miny then r:=maxy-miny;
while l<r do
begin
mid:=(l+r)shr 1;
fillchar(v,sizeof(v),false);
fillchar(st,sizeof(st),0);
if check(mid,1) then r:=mid
else l:=mid+1;
end;
write(l);
end;

begin
init;
end.


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

历史上的今天

评论

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

页脚

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