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 1173. Lazy Snail

Whats wrong with my algorithm or code?
Posted by Locomotive 10 Feb 2003 18:22
First i calculate the degree between wally house and every friend by
procedure ATG and then sort friends by their degree...

Type
Point               =record
x,y,d             :real;
ID                :Integer;
end;
Var
a                   :array[0..1000] of point;
n,i                 :integer;

function partition(first,last:integer):integer;
Var
t                   :point;
i,j                 :integer;
x                   :real;
begin
i:=first-1;
j:=last+1;
x:=a[first].d;
while true do
begin
repeat inc(i);
until a[i].d<=x;
repeat dec(j);
until a[j].d>=x;
if i<j then begin
t:=a[i]; a[i]:=a[j]; a[j]:=t; end
else begin
partition:=j; exit; end;
end;
end;

Procedure qsort(first,last:integer);
Var
w                   :integer;
begin
if first<last then
begin
w:=partition(first,last);
qsort(first,w);
qsort(w+1,last);
end;
end;

Function ATG(x:integer):real;
Var
dx,dy,k             :real;
begin
dx:=a[x].x-a[0].x;
dy:=a[x].y-a[0].y;
if dx=0 then
k:=90
else
k:=arctan(dy/dx)/pi*180;
if (k<0) or ((k=0) and (dx<0)) then k:=k+180;
if dy<0 then k:=k+180;
atg:=k;
end;

begin
for i:=1 to n do
begin
a[i].d:=ATG(i);
end;
qsort(1,n);
writeln(0);
for i:=1 to n do
writeln(a[i].Id);
writeln(0);
end.
Wally's house may be at center, so, your program doesn't work (-)
Posted by Miguel Angel 10 Feb 2003 21:58
> First i calculate the degree between wally house and every friend
by
> procedure ATG and then sort friends by their degree...
>
> Type
>   Point               =record
>     x,y,d             :real;
>     ID                :Integer;
>   end;
> Var
>   a                   :array[0..1000] of point;
>   n,i                 :integer;
>
> function partition(first,last:integer):integer;
> Var
>   t                   :point;
>   i,j                 :integer;
>   x                   :real;
> begin
>   i:=first-1;
>   j:=last+1;
>   x:=a[first].d;
>   while true do
>   begin
>     repeat inc(i);
>     until a[i].d<=x;
>     repeat dec(j);
>     until a[j].d>=x;
>     if i<j then begin
>       t:=a[i]; a[i]:=a[j]; a[j]:=t; end
>     else begin
>       partition:=j; exit; end;
>   end;
> end;
>
> Procedure qsort(first,last:integer);
> Var
>   w                   :integer;
> begin
>   if first<last then
>   begin
>     w:=partition(first,last);
>     qsort(first,w);
>     qsort(w+1,last);
>   end;
> end;
>
> Function ATG(x:integer):real;
> Var
>   dx,dy,k             :real;
> begin
>   dx:=a[x].x-a[0].x;
>   dy:=a[x].y-a[0].y;
>   if dx=0 then
>     k:=90
>   else
>     k:=arctan(dy/dx)/pi*180;
>   if (k<0) or ((k=0) and (dx<0)) then k:=k+180;
>   if dy<0 then k:=k+180;
>   atg:=k;
> end;
>
> begin
>   for i:=1 to n do
>   begin
>     a[i].d:=ATG(i);
>   end;
>   qsort(1,n);
>   writeln(0);
>   for i:=1 to n do
>     writeln(a[i].Id);
>   writeln(0);
> end.
>
but it works... i calculate degree in range 0..360
Posted by Locomotive 11 Feb 2003 12:41
may you tell me a test????
See(+)
Posted by Miguel Angel 12 Feb 2003 01:40
Think of the following

Input:
0 0
3
1  0 1
0 -1 2
1 -1 3
Output:
0
2
3
1
0

Luck!
Hey Special thanks
Posted by Locomotive 14 Feb 2003 00:22
at last i correct my solution here:
if there where two friend with house number i and i+1 which
a[i+1]-a[i]>180 (it is obvious that there will be at last just one of
this type) then path be
i+1-i+2-...-n-...-1-2-3-...-i
Thanks a lit for another AC :)
yours
Aidin_n7@hotmail.com