讨论 / 给跪了 排序+贪心
voleking 2013-10-16 22:27:00
点我顶贴 收藏 删除
const

exp:double=1e-8;

type

cover=record

l,r:double;

end;

var

i,j,k,m,n,w,h,x0,y0,ai:longint;

line:array[1..100000]of cover;

ans:longint;

r,rr:double;

procedure qsort(l,r:longint);

var

i,j:longint;

x:double;

tmp:cover;

begin

i:=l;j:=r;x:=line[(i+j)div 2].l;

repeat

while line[i].l<x do inc(i);

while line[j].l>x do dec(j);

if i<=j then

begin

tmp:=line[i];line[i]:=line[j];line[j]:=tmp;

inc(i);dec(j);

end;

until i>j;

if i<r then qsort(i,r);

if j>l then qsort(l,j);

end;

function max(a,b:double):double;

begin

if a>b then exit(a) else exit(b);

end;

begin

readln(w,h,n);

for i:=1 to n do

begin

readln(x0,y0,ai);

r:=(h-y0)*sin(ai*pi/360)/cos(ai*pi/360);

if x0-r<0 then line[i].l:=0 else line[i].l:=x0-r;

if x0+r>w then line[i].r:=w else line[i].r:=x0+r;

end;

qsort(1,n);

r:=0;ans:=0;

for i:=1 to n do

begin

rr:=r+exp;

j:=1;

while(j<=n)and(line[j].l<=rr)do

begin

r:=max(r,line[j].r);

inc(j);

end;

if r>rr then inc(ans)

else begin writeln(-1);exit;end;

if r>=w then break;

end;

writeln(ans);

end.

有空的看看吧,我觉得是正解了

#1 ak8877@2013-10-04 09:23:00
回复 删除
。。。貌似是直接翻译了发题解的那哥们的C++代码啊
#2 wangshuoyu@2013-10-16 22:27:00
回复 删除
我也喜欢c/c++转FP

查看更多回复
提交回复