ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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
  readln(a[0].x,a[0].y);
  readln(n);
  for i:=1 to n do
  begin
    readln(a[i].x,a[i].y,a[i].ID);
    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
>   readln(a[0].x,a[0].y);
>   readln(n);
>   for i:=1 to n do
>   begin
>     readln(a[i].x,a[i].y,a[i].ID);
>     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