ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1332. Genie Bomber

why wa?
Posted by Shteiner Sergei 16 Oct 2004 16:05
Is test#13 correct?
Here is my code
Posted by Shteiner Sergei 16 Oct 2004 16:11
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
for i:=1 to n do Read (x[i],y[i]);
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.
Re: Here is my code
Posted by Alex Svetkin [OrelSTU] 21 Oct 2004 01:44
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?
Re: why wa?
Posted by Aleksey Meshnikovsky 21 Oct 2004 02:49
Try to change break to continue;
Re: why wa?
Posted by SSAU_Stukalov 21 Oct 2004 12:16
I have WA at test 19.
Re: why wa?
Posted by Alex Svetkin [OrelSTU] 24 Oct 2004 16:07
>> Try to change break to continue;
Thanks! :)
Re: Here is my code
Posted by SSAU_Stukalov 19 Feb 2005 19:56
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;).
Re: Here is my code
Posted by Vasya 21 Feb 2005 06:09
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