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

Общий форум

PROBLEM 1058. Why I get WA??????!!!(+)
Послано Nazarov Denis (nsc2001@rambler.ru) 8 мар 2002 11:13
Program t1058;{$N+}

Const MaxN = 200;
      Eps  = 1E-15;

Type  TPoint = record X,Y : extended end;
      TPoly = record
        V : array[1..MaxN]of TPoint;
        N : integer;
       end;

Var   CPoly     : TPoly;
      i,j       : integer;

Function GetDist(A,B : TPoint) : extended;
 begin
  GetDist:=Sqrt(Sqr(A.X-B.X)+Sqr(A.Y-B.Y));
 end;

Function GetS(A : TPoly; N : integer) : extended;
Var S   : extended;
    i   : integer;
 begin
  A.V[N+1]:=A.V[1];
  S:=0;
  for i:=1 to N do S:=S+(A.V[i].X-A.V[i+1].X)*(A.V[i].Y+A.V[i+1].Y);
  S:=S/2;
  GetS:=abs(S);
 end;

Procedure MakeMedian(A : TPoly; N : integer;Var last : integer; Var
C : TPoint);
Var i,j,ls : integer;
    s,ps   : extended;
    l,r,m  : TPoint;
    New    : TPoly;
 begin
  ps:=GetS(A,N);
  for ls:=2 to N do
   if 2*GetS(A,ls)>ps then break;
  last:=ls;
  l:=A.V[last-1];
  r:=A.V[last];
  New:=A;
  While True do begin
    m.X:=(l.X+r.X)/2;
    m.Y:=(l.Y+r.Y)/2;
    New.V[last]:=m;
    s:=GetS(New,last);
    if 2*s-ps>Eps then r:=m else
    if 2*s-ps<-Eps then l:=m else break;
   end;
  C:=m;
 end;

Function MakeDist(A : TPoly; N,Cur : integer) : extended;
Var i,j   : integer;
    P     : TPoly;
    Ans   : TPoint;
 begin
  j:=Cur-1;
  for i:=1 to N do begin
    j:=j+1;
    if j>N then j:=1;
    P.V[i]:=A.V[j];
   end;
  MakeMedian(P,N,j,Ans);
  MakeDist:=GetDist(P.V[1],Ans);
 end;

Function FindBest(A : TPoly; last : integer) : extended;
Var i,j      : integer;
    P        : TPoly;
    l,r,m    : TPoint;
    ls,rs,ms : extended;
 begin
  j:=last-1;
  for i:=2 to A.N+1 do begin
    j:=j+1;
    if j>A.N then j:=1;
    P.V[i]:=A.V[j];
   end;
  P.N:=A.N+1;
  l:=P.V[P.N];
  r:=P.V[2];
  While True do begin
    m.X:=(l.X+r.X)/2;
    m.Y:=(l.Y+r.Y)/2;
    P.V[1]:=m;
    ms:=MakeDist(P,P.N,1);
    P.V[1]:=l; ls:=MakeDist(P,P.N,1);
    P.V[1]:=r; rs:=MakeDist(P,P.N,1);
    if abs(ls-ms)<Eps then break;
    if ls>rs then begin
      if ms>rs then l:=m else r:=m;
     end else begin
      if ms>ls then r:=m else l:=m;
     end;
   end;
  FindBest:=ms;
 end;

Procedure Solve;
Var i,j,ok_i   : integer;
    m          : array[0..MaxN]of extended;
    b1,b2      : extended;
    Ans        : String[100];
 begin
  for i:=1 to CPoly.N do
   m[i]:=MakeDist(CPoly,CPoly.N,i);
  m[0]:=m[CPoly.N];
  m[CPoly.N+1]:=m[1];
  for j:=1 to CPoly.N do
   if m[j]<m[j-1] then
    if m[j]<m[j+1] then break;
  b1:=FindBest(CPoly,1);
  for j:=2 to CPoly.N do begin
   b2:=FindBest(CPoly,j+1);
   if b2<b1 then b1:=b2;
  end;
  if b1<b2 then Str(b1:0:8,Ans) else Str(b2:0:8,Ans);
  While Ans[length(Ans)]='0' do delete(Ans,length(Ans),1);
  if Ans[length(Ans)]='.' then delete(Ans,length(Ans),1);
  Writeln(Ans);
 end;

begin
 Read(CPoly.N);
 for i:=1 to CPoly.N do Read(CPoly.V[i*2].X,CPoly.V[i*2].Y);
 for i:=2 to CPoly.N do begin
   CPoly.V[i*2-1].X:=(CPoly.V[i*2-2].X+CPoly.V[i*2].X)/2;
   CPoly.V[i*2-1].Y:=(CPoly.V[i*2-2].Y+CPoly.V[i*2].Y)/2;
  end;
 CPoly.V[1].X:=(CPoly.V[CPoly.N*2].X+CPoly.V[2].X)/2;
 CPoly.V[1].Y:=(CPoly.V[CPoly.N*2].Y+CPoly.V[2].Y)/2;
 CPoly.N:=CPoly.N*2;
 Solve;
end.