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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1038】【ZJOI2008】【瞭望塔】  

2014-02-28 18:46:25|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   首先能看到某段坡肯定在这段坡朝向上面无穷远处的半平面内,所以我们先求半平面交。就得到了一个凸壳。
   这个凸壳是下凸的,贪心的想,答案就是这个凸包上的边界线上的点。
   考虑凸壳的一条边和它下面的,显然答案在 所有凸壳的交点以及地面上的转折点的X内。
   所以这题就可以AC了。
   求这种特殊的半平面交 可以 参照HNOI2008那个水平可见直线的方法,然后单调栈之后求出交点,然后每一个都暴力枚举一下,二分求它的底部或者顶部所在的直线,再求高度,复杂度O(NlogN)
   PS:虽然这次是说的很轻松,但是写起来还是觉得非常不爽的....
   我们对于每一条直线用两点式表示,首先求半平面交,然后从左到右求出凸壳交点,最后再每一个节点枚举一下,如果在凸壳上就二分出它所在的山上的直线,求出底部,如果在山上就二分出它在凸壳上的直线,求出顶部,两种求出来高度取最大即可。
   
   这次写的要多萎有多萎.....各种乱搞各种YY各种乱码感各种稀里糊涂各种错误各种想吐...最后求交点的时候如果两条线平行咱把交点设为无穷远处(大概10^30),总算A了....
=============================================

program bzoj1038;
type point=record
     x,y:double;
     end;
     line=record
     k,b:double;
     end;

var x,cr:array[0..2010]of point;
    l,st:array[0..2010]of line;
    n:longint;

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

function det(a,b,c,d:double):double;
begin
  exit(d*a-b*c);
end;

function get(a,b:line):point;
var p:point;
    d,dx,dy:double;
begin
  if a.k=b.k then
   begin
     p.x:=1e30;
     p.y:=1e30;
     exit(p);
   end; 
  d:=det(a.k,-1,b.k,-1);
  dx:=det(-a.b,-1,-b.b,-1);
  dy:=det(a.k,-a.b,b.k,-b.b);
  p.x:=dx/d;
  p.y:=dy/d;
  exit(p);
end;


procedure qsort(ll,r:longint);
var i,j:longint;
    x,z:double;
    y:line;
begin
  i:=ll;j:=r;
  x:=l[(ll+r)shr 1].k;
  z:=l[(ll+r)shr 1].b;
  repeat
    while (l[i].k<x)or((l[i].k=x)and(l[i].b<z)) do inc(i);
    while (l[j].k>x)or((l[j].k=x)and(l[j].b>z)) do dec(j);
    if i<=j then
     begin
       y:=l[i];l[i]:=l[j];l[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>ll then qsort(ll,j);
end;

procedure init;
var i,j,top,sta:longint;
    p:point;
    y,ans:double;
begin
  read(n);
  for i:=1 to n do
   read(x[i].x);
  for i:=1 to n do
   read(x[i].y);
  for i:=2 to n do
   begin
     l[i-1].k:=(x[i].y-x[i-1].y)/(x[i].x-x[i-1].x);
     l[i-1].b:=det(x[i].x,x[i].y,x[i-1].x,x[i-1].y)/(x[i].x-x[i-1].x);
   end;
  qsort(1,n-1);
  top:=1;
  while l[top].k=l[top+1].k do inc(top);
  st[1]:=l[top];
  sta:=top+1;
  top:=1;
  if n-1>=2 then
   begin
    st[2]:=l[2];
    inc(top);
    inc(sta);
   end;
  if top=2 then cr[2]:=get(st[top],st[top-1]);
  for i:=sta to n-1 do
   begin
     if l[i].k=st[top].k then dec(top);
     p:=get(l[i],st[top]);
     while (top>1)and(p.x<=cr[top].x)do
      begin
        dec(top);
        p:=get(l[i],st[top]);
      end;
     inc(top);
     st[top]:=l[i];
     cr[top]:=p;
   end;
  sta:=2;
  ans:=1e30;
  while cr[sta].x<x[1].x do
   inc(sta);
  while cr[top].x>x[n].x do
   dec(top);
  for i:=2 to n do
   begin
     l[i-1].k:=(x[i].y-x[i-1].y)/(x[i].x-x[i-1].x);
     l[i-1].b:=det(x[i].x,x[i].y,x[i-1].x,x[i-1].y)/(x[i].x-x[i-1].x);
   end;
  for i:=sta to top do
   begin
     for j:=1 to n do
      if x[j].x>cr[i].x then break;
     y:=l[j-1].k*cr[i].x+l[j-1].b;
     ans:=min(ans,cr[i].y-y);
   end;
  for i:=1 to n do
   begin
     for j:=sta to top do
      if cr[j].x>x[i].x then break;
     if cr[j].x>x[i].x then
     y:=st[j-1].k*x[i].x+st[j-1].b
     else
     y:=st[j].k*x[i].x+st[j].b;
     ans:=min(ans,y-x[i].y);
   end;
  write(ans:0:3);
end;

begin
  init;
end.







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

历史上的今天

评论

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

页脚

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