ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1173. Lazy Snail

Whats wrong with my algorithm or code?
Послано Locomotive 10 фев 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 (-)
Послано Miguel Angel 10 фев 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
Послано Locomotive 11 фев 2003 12:41
may you tell me a test????
See(+)
Послано Miguel Angel 12 фев 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 фев 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