level 11
风云幻之翼
楼主
poj1328 的贪心,(雷达站)
感觉我写的跟标准的一样啊
就是WA。。![[委屈]](/static/emoticons/u59d4u5c48.png)
program poj1328;
var n,d,ca,i,ans,x,y:longint;
s:array[1..2000,0..1]of real;
low:array[1..10000]of longint;
procedure rar(x,y,k:longint);
var dis,left,right:real;
begin
dis:=sqrt(sqr(d)-sqr(y));
left:=x-dis;
right:=x+dis;
s[k,0]:=left;
s[k,1]:=right;
end;
procedure sort(l,r:longint);
var i,j:longint; t1,t2:real;
begin
i:=l;j:=r;t1:=s[l,0];t2:=s[l,1];
while (i<j) do
begin
while (i<j)and(t1<=s[j,0]) do dec(j);
if i<j then begin s[i,0]:=s[j,0];s[i,1]:=s[j,1];inc(i) end;
while (i<j)and(s[i,0]<=t1) do inc(i);
if i<j then begin s[j,0]:=s[i,0];s[j,1]:=s[i,1];dec(j) end;
end;
s[i,0]:=t1; s[i,1]:=t2;
if i-l>1 then sort(l,i-1);
if r-i>1 then sort(i+1,r);
end;
procedure main(var ans:longint);
var i,m:longint; max:real;
begin
m:=1;
max:=s[1,1];
for i:=2 to n do
if max<s[i,0] then begin
m:=m+1;
max:=s[i,1];
end
else if max>s[i,1] then max:=s[i,1];
ans:=m;
end;
procedure putout(c:longint);
begin
writeln(*Case *,c,*:*,low[c]);
end;
begin
ca:=1;
readln(n,d);
repeat
for i:=1 to n do
begin
readln(x,y);
rar(x,y,i);
end;
sort(1,n);
main(ans);
low[ca]:=ans;
ca:=ca+1;
readln(n,d);
until (n=0);
for i:=1 to ca-1 do putout(i);
end.
2014年11月16日 09点11分
1
感觉我写的跟标准的一样啊
就是WA。。
program poj1328;
var n,d,ca,i,ans,x,y:longint;
s:array[1..2000,0..1]of real;
low:array[1..10000]of longint;
procedure rar(x,y,k:longint);
var dis,left,right:real;
begin
dis:=sqrt(sqr(d)-sqr(y));
left:=x-dis;
right:=x+dis;
s[k,0]:=left;
s[k,1]:=right;
end;
procedure sort(l,r:longint);
var i,j:longint; t1,t2:real;
begin
i:=l;j:=r;t1:=s[l,0];t2:=s[l,1];
while (i<j) do
begin
while (i<j)and(t1<=s[j,0]) do dec(j);
if i<j then begin s[i,0]:=s[j,0];s[i,1]:=s[j,1];inc(i) end;
while (i<j)and(s[i,0]<=t1) do inc(i);
if i<j then begin s[j,0]:=s[i,0];s[j,1]:=s[i,1];dec(j) end;
end;
s[i,0]:=t1; s[i,1]:=t2;
if i-l>1 then sort(l,i-1);
if r-i>1 then sort(i+1,r);
end;
procedure main(var ans:longint);
var i,m:longint; max:real;
begin
m:=1;
max:=s[1,1];
for i:=2 to n do
if max<s[i,0] then begin
m:=m+1;
max:=s[i,1];
end
else if max>s[i,1] then max:=s[i,1];
ans:=m;
end;
procedure putout(c:longint);
begin
writeln(*Case *,c,*:*,low[c]);
end;
begin
ca:=1;
readln(n,d);
repeat
for i:=1 to n do
begin
readln(x,y);
rar(x,y,i);
end;
sort(1,n);
main(ans);
low[ca]:=ans;
ca:=ca+1;
readln(n,d);
until (n=0);
for i:=1 to ca-1 do putout(i);
end.