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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2732】【Hnoi2012】【射箭】  

2014-04-23 09:11:41|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:平面上有N个与y轴垂直的箭靶子,一支膜拜牛顿的箭按抛物线从原点(0,0)飞出,要求如果要击中第i个靶子,那么前I-1个靶子也必须都射穿【这里的前i个是按读入的顺序】。求最多能射穿的靶子数。

   = = 以前看不出是半平面交...现在才知道是它...0.0
   假设咱们要能击中某个靶子【x,y1,y2】(这个靶子在x处,最低y1,最高y2),那么咱们设轨迹是 ax^2+bx=y(为什么木有看到c?0.0因为这个经过(0,0)恩....)那么就有不等式:
    y1<=ax^2+bx<=y2,
    咱们枚举可以射穿前多少箭靶
    然后就有一大堆这样的不等式了...
    咱们又知道x,所以就有 x^2*a+x*b-y1>=0 和 x^2*a+x*b-y2<=0 两个不等式,咱们把a,b看做平面坐标的x,y两种坐标,然后这就是一个半平面了....然后a,b有解实际上就是半平面非空...><好神奇额...
    然后貌似就是每次动态添加两个半平面?不行额..O(nlogn)的半平面必须要极角排序?所以这个显然不能这样做...不过O(n^2)又耗时了,所以可以二分答案。这样子复杂度就是O(nlog^2n)

    【话说偷看了ydc君的题解 【题解传送门】,发现精度需要调到 1e-16...】

     听说还有O(n)的随机增量法...0.0不知道它和最小覆盖圆是不是亲戚额... 不过具体的可以去看 Vfk君的 随机增量 来虐此题.... 

     【另外这题看到某c++er 80行+代码O(nlog^2n)直接A了,让咱经常手抖的蒟蒻情何以堪...= =】

      然后就是一些无聊的实现环节...首先读入的时候咱们就可以构造半平面了...但是貌似问题就是咱只会两点式的= =,所以需要自己转化,即从这种解析式变成两点式,实际上咱们可以先求出两个点,然后把看b的系数是否小于0,小于0的话咱们就给其中一个点的y-1,否则y+1,就可以得到一个在可行域内的点。然后咱们用两个点去叉它,得到顺序。

     这道题如果这样写的话就会TLE额...0.0 然后有几个优化可以加进去就可以AC了。

     第一个就是所有的半平面的象限可以一开始就计算出来,没必要在最后极角排序的时候来做。

     第二点,感谢drj君的题解 一个非常好的优化  咱们的复杂度O(nlogn^2)实际上可以将它降为O(nlogn),因为每一次求半平面交的障碍实际上在于排序的O(nlogn),也就是说如果在求半平面交的时候已经排好序的话就可以把复杂度降到O(nlogn),而这个顺序实际上咱们可以一开始读入时候就把所有的半平面按极角序给排出来,然后每一次按照那个顺序扫描出当前需要的即可....【给每一个半平面标上一个读入时候的编号,然后每一次只需要找编号<=K的半平面出来即可,显然它们的顺序就是扫描时候的先后顺序】
这样复杂度变成了O(nlogn),咱最慢的点便是0.93s跑完了【原来是3.2s多额...】

=================================

program hnoi2012day2b;
const maxn=400010;
eps=1e-19;

type point=record
x,y:double;
end;
poly=record
x,y,w:point;
ww,bh:longint;
end;

var po,ini,que:array[0..maxn]of poly;
p:array[0..maxn]of point;
n,tot:longint;

operator -(var a,b:point)c:point;
begin
c.x:=a.x-b.x;c.y:=a.y-b.y;
end;

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

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

function det(a,b:point):double;
begin
exit(a.x*b.y-a.y*b.x);
end;

function cal(a,b,c:int64):poly;
var p1,p2,o,t:point;
ans:poly;
begin
if c<>0 then
begin
p1.x:=0;p1.y:=-c/b;
p2.y:=0;p2.x:=-c/a;
end
else
begin
p1.x:=0;p1.y:=0;
p2.x:=-1;p2.y:=a/b;
end;
o.x:=p2.x;
if b<0 then o.y:=p2.y-1
else o.y:=p2.y+1;
if det(p1,p2,p1,o)-eps<0 then
begin
t:=p1;p1:=p2;p2:=t;
end;
ans.x:=p1;ans.y:=p2;
ans.w.x:=p2.x-p1.x;
ans.w.y:=p2.y-p1.y;
exit(ans);
end;

function cal(p:point):longint;
begin
if abs(p.x)-eps<0 then
if p.y>0 then exit(1)
else exit(3);
if abs(p.y)-eps<0 then
if p.x>0 then exit(4)
else exit(2);
if (p.x>0)and(p.y>0) then exit(1);
if (p.x<0)and(p.y>0) then exit(2);
if (p.x<0) then exit(3)
else exit(4);
end;

function get(p,q:poly):point;
var d1,dx,t:double;
ans:point;
begin
d1:=det(p.w.x,-q.w.x,p.w.y,-q.w.y);
dx:=det(q.x.x-p.x.x,-q.w.x,q.x.y-p.x.y,-q.w.y);
t:=dx/d1;
ans.x:=p.x.x+t*p.w.x;
ans.y:=p.x.y+t*p.w.y;
exit(ans);
end;

function cmp(u,v:poly):boolean;
begin
if u.ww<>v.ww then
if u.ww<v.ww then exit(true)
else exit(false);
if det(u.w.x,u.w.y,v.w.x,v.w.y)-eps>0 then exit(true)
else exit(false);
end;

procedure qsort(l,r:longint);
var i,j:longint;x,y:poly;
begin
i:=l;j:=r;
x:=ini[(l+r)shr 1];
repeat
while cmp(ini[i],x) do inc(i);
while cmp(x,ini[j]) do dec(j);
if i<=j then
begin
y:=ini[i];ini[i]:=ini[j];ini[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

function check(n:longint):boolean;
var i,l,r,j:longint;
begin
j:=0;
for i:=1 to tot do
if ini[i].bh<=n then
begin
inc(j);
po[j]:=ini[i];
end;
l:=0;r:=0;
que[l]:=po[1];
for i:=2 to n do
begin
while (l<r)and(det(po[i].w,p[r-1]-po[i].x)+eps<0)do dec(r);
while (l<r)and(det(po[i].w,p[l]-po[i].x)+eps<0)do inc(l);
inc(r);
que[r]:=po[i];
if abs(det(que[r].w,que[r-1].w))-eps<0 then
begin
dec(r);
if det(que[r].w,po[i].x-que[r].x)-eps>0 then
que[r]:=po[i];
end;
if (l<r) then p[r-1]:=get(que[r-1],que[r]);
end;
while (l<r)and(det(que[l].w,p[r-1]-que[l].x)+eps<0)do dec(r);
if r-l<=1 then exit(false);
exit(true);
end;

procedure init;
var i,l,r,mid:longint;
a,b,x,y1,y2:int64;
begin
read(n);
tot:=4;
ini[1].x.x:=-1e10;ini[1].x.y:=-1e10;
ini[1].y.x:=1e10;ini[1].y.y:=-1e10;
ini[2].x.x:=1e10;ini[2].x.y:=-1e10;
ini[2].y.x:=1e10;ini[2].y.y:=1e10;
ini[3].x.x:=1e10;ini[3].x.y:=1e10;
ini[3].y.x:=-1e10;ini[3].y.y:=1e10;
ini[4].x.x:=-1e10;ini[4].x.y:=1e10;
ini[4].y.x:=-1e10;ini[4].y.y:=-1e10;
for i:=1 to 4 do
begin
ini[i].w.x:=ini[i].y.x-ini[i].x.x;
ini[i].w.y:=ini[i].y.y-ini[i].x.y;
ini[i].ww:=cal(ini[i].w);
ini[i].bh:=i;
end;
for i:=1 to n do
begin
read(x,y1,y2);
inc(tot);ini[tot]:=cal(x*x,x,-y1);
ini[tot].ww:=cal(ini[tot].w);
ini[tot].bh:=tot;
inc(tot);ini[tot]:=cal(-x*x,-x,y2);
ini[tot].ww:=cal(ini[tot].w);
ini[tot].bh:=tot;
end;
qsort(1,tot);
l:=1;r:=n;
while l<r do
begin
mid:=(l+r+1)shr 1;
if check(mid shl 1+4) then l:=mid
else r:=mid-1;
end;
write(l);
end;

begin
init;
end.


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

历史上的今天

评论

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

页脚

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