PROBLEM 1058. Why I get WA??????!!!(+)
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.