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

Show all messages Hide all messages

Whats wrong with my algorithm or code? 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.
> 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.
>
may you tell me a test????
See(+) 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 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