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

Обсуждение задачи 1588. Ямайка

What's the test 8
Послано yuyan 18 мар 2009 06:07
    Why I WA on #8?I can't find what's wrong with my program.
    Here is my code:
    program jamaica;
const
  maxn=310;
var
  k,b,l:array [0..maxn*maxn] of extended;
  x,y:array [0..maxn] of int64;
  i,j,m,n,min,max:longint;
  ans,d:double;
procedure init;
  begin
    readln(n);
    for i:=1 to n do readln(x[i],y[i]);
  end;
procedure qsort(head,tail:longint);
  var
    i,j,t,k:longint;
  begin
    if head>=tail then exit;
    i:=head;j:=tail;
    t:=x[(i+j) shr 1];
    repeat
     while x[j]>t do dec(j);
     while x[i]<t do inc(i);
     if i<=j
       then begin
              k:=x[i];x[i]:=x[j];x[j]:=k;
              k:=y[i];y[i]:=y[j];y[j]:=k;
              inc(i);dec(j);
            end;
    until i>=j;
    qsort(head,j);
    qsort(i,tail);
  end;
procedure sort(head,tail:longint);
  var
    i,j:longint;
    x,y,t:double;
  begin
    if head>=tail then exit;
    i:=head;j:=tail;
    x:=k[(i+j) shr 1];y:=b[(i+j) shr 1];
    repeat
     while (k[j]-x>1e-8) or (abs(k[j]-x)<1e-8) and (b[j]-y>1e-8) do dec(j);
     while (k[i]-x<-1e-8) or (abs(k[i]-x)<1e-8) and (b[i]-y<-1e-8) do inc(i);
     if i<=j
       then begin
              t:=k[i];k[i]:=k[j];k[j]:=t;
              t:=b[i];b[i]:=b[j];b[j]:=t;
              t:=l[i];l[i]:=l[j];l[j]:=t;
              inc(i);dec(j);
            end;
    until i>=j;
    sort(head,j);
    sort(i,tail);
  end;
procedure solve;
  begin
    qsort(1,n);
    ans:=0;
    min:=y[1];max:=y[1];
    for i:=2 to n do
      if x[i]<>x[i-1]
        then begin
               ans:=ans+max-min;
               max:=y[i];min:=y[i];
             end
        else begin
               if y[i]>max then max:=y[i];
               if y[i]<min then min:=y[i];
             end;
    ans:=ans+max-min;
    m:=0;
    for i:=1 to n-1 do
      for j:=i+1 to n do
        if x[i]<>x[j]
          then begin
                 inc(m);k[m]:=(y[j]-y[i])/(x[j]-x[i]);b[m]:=y[i]-k[m]*x[i];
                 l[m]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
               end;
    sort(1,m);
    d:=l[1];
    for i:=2 to m do
      if (k[i]<>k[i-1]) or (b[i]<>b[i-1])
        then begin
               ans:=ans+d;
               d:=l[i];
             end
        else begin
               if l[i]>d then d:=l[i];
             end;
    ans:=ans+d;
  end;
begin
  init;
  solve;
  writeln(round(ans));
end.