|
|
back to boardIs test#13 correct? const e=0.00001;
var n,i,j,z,s,c:longint;
r,r1,rx,ry,a,b,norm,w,l,x1,y1:real;
x,y:array [1..100] of real;
function check (x,y,r,x1,y1:real):boolean;
begin
if sqr (x-x1)+sqr (y-y1)<=sqr (r)+e then check:=true else check:=false;
end;
begin
Read (n);
for i:=1 to n do Read (x[i],y[i]);
Read (r); Read (r1);
r:=r-r1;
if r<0 then begin write (0); halt; end;
if r=0 then begin write (1); halt; end;
if n=1 then begin write (1); halt; end;
for i:=1 to n do
for j:=i+1 to n do begin
l:=sqr (x[i]-x[j]) + sqr (y[i]-y[j]);
l:=l/4;
if sqr(r)<l-e then break;
l:=sqrt (l);
w:=sqrt (sqr (r)-sqr (l));
x1:=(x[i]+x[j])/2; y1:=(y[i]+y[j])/2;
a:=(y[i]-y[j]); b:=(x[j]-x[i]);
norm:=sqrt (sqr(a)+sqr(b));
rx:=x1+a*w/norm; ry:=y1+b*w/norm;
s:=2;
for z:=1 to n do if (z<>i) and (z<>j) then if check (rx,ry,r,x[z],y[z]) then inc (s);
if s>c then c:=s;
a:=-(y[i]-y[j]); b:=-(x[j]-x[i]);
norm:=sqrt (sqr(a)+sqr(b));
rx:=x1+a*w/norm; ry:=y1+b*w/norm;
s:=2;
for z:=1 to n do if (z<>i) and (z<>j) then if check (rx,ry,r,x[z],y[z]) then inc (s);
if s>c then c:=s;
end;
Write (c);
end. I use the same alogrithm and get WA at test #12.
Have you ACed it? If yes, could you tell me where is the trick? First, in the beginning of the program you must c:=1;
Second, you must change break to continue (if sqr(r)<l-e then break;). Hello.
I had not red all you program-it is difficult,but i think you algorithm is bad,as for me i rassmatrival troiki to4ek,nahodil centr opis okrugnosti i t d.
No odna tvoa o6ibka vidna-pri sravnenii vewestvennih 4isel ti usilivae6 neravenstvo, a ne oslabl`ae6:
if sqr(r)<l-e then
Nado:if sqr(r)<l+e then Hallo, Vasya!
Ya delayu to zhe samoe.
And I got ACed. I also have WA at test #13 i dont't understand why.
Pls HELP me! :(
Edited by author 30.01.2006 21:37
Edited by author 30.01.2006 21:38 Try to change break to continue; >> Try to change break to continue;
Thanks! :) |
|
|
