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

Common Board

PROBLEM 1058. Why I get WA??????!!!(+)
Posted by Nazarov Denis (nsc2001@rambler.ru) 8 Mar 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.