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

Общий форум

Help!(p1065)
Послано qaztz 4 апр 2002 18:48
I've got trouble in problem 1065.

Here is my program:
{$q+,n+}
var n,m,a,d,e:integer; min,j:extended;
    b:array[0..50,1..2] of extended;
    c:array[1..1000,1..2] of extended;
    f:array[1..50,1..50] of boolean;
    g:array[0..50] of shortint;
    h:array[1..50,1..2] of extended;
    i:array[1..50,1..50] of extended;
begin
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  readln(n,m);
  for a:=1 to n do readln(b[a,1],b[a,2]);
  for a:=1 to m do readln(c[a,1],c[a,2]);
  for a:=1 to n do for d:=1 to n do
    if a<>d then begin
      f[a,d]:=true;
      for e:=1 to m do
        if (b[d,1]-b[a,1])*(c[e,2]-b[a,2])-(b[d,2]-b[a,2])*(c[e,1]-b
[a,1])>=0
          then begin
            f[a,d]:=false; break;
          end;
    end;
  for a:=1 to n-1 do for d:=a+1 to n do begin
    i[a,d]:=sqrt(sqr(b[a,1]-b[d,1])+sqr(b[a,2]-b[d,2]));
    i[d,a]:=i[a,d];
  end;
  for a:=1 to n do g[a]:=a;
  min:=1e20;
  for a:=1 to n do begin
    fillchar(h,sizeof(h),0);
    for d:=2 to n do begin
      if f[g[1],g[d]] then h[d,1]:=i[g[1],g[d]]
        else h[d,1]:=1e20;
      h[d,2]:=1e20;
    end;
    for d:=3 to n do for e:=2 to d-1 do
      if f[g[e],g[d]] then begin
        if h[e,1]<h[e,2] then j:=h[e,1]
          else j:=h[e,2];
        if h[d,2]>j+i[g[e],g[d]] then h[d,2]:=j+i[g[e],g[d]];
      end;
    for d:=3 to n do
      if f[g[d],g[1]] and(h[d,2]+i[g[1],g[d]]<min) then
        min:=h[d,2]+i[g[1],g[d]];
    for d:=1 to n do g[d-1]:=g[d];
    g[n]:=g[0];
  end;
  writeln(min:0:2);
  close(input); close(output);
end.

Thank you!