Wa3 - answer is 0.00. there you should check the longest block ;)

I counted radius with precision 1e-10, upper bound is 1e6.
P.s. dont forget cases there center of circle is outside(like sample)

For the max test (a hundred 100's) the answer is 7955128.99. For ninety nine 1m sides and one 98m side it's 397.86.
Use this to check your precision.

infin = 100000000 - wa14.
infin = 1000000 - ac.

Try

3
3
4
5

The answer should be 6.00

i used 1e8 first and got wa14
latter used n*(sum of edge lengths) and got ac.

i found that for test 14 the curve goes up and at r=200.75 touches x axis then goes up until
x=around 450 then down again with asymptote as x axis. so i tried to use tenary search to find upper bound but it does not always work. why n*sum of lengths work? is it weak tests or can somebody prove optimal upper bound?

please, help me understand.
thanks in advance.

Isn't answer 40 on T1? trapeze with bases 10 and 4.

Edited by author 27.03.2011 03:35

I have got the data of  this problem !
Do you want it? Contact Me, and I will give it to you, my dear!

My Email : MartinKanglh@hotmail.com

Do Remember Me! My name is Martin.Kang

Something about this problem :
the precision of this problem is very abnormality, you must make it as 1e-8, and make the maximal answer as 1e8, then you can pass the data and get accept.

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535

double a[101];
int n;

void init()
{
int i,k;
double t;
scanf("%d",&n);
k=1;
for (i=1;i<=n;i++)
 {
 scanf("%lf",&a[i]);
 if (a[i]>a[k])
  k=i;
 }
t=a[1];
a[1]=a[k];
a[k]=t;
}

double hl(double r,int k)
{
double p;
double s;
p=(a[k]+r+r)/2;
s=p*(p-a[k])*(p-r)*(p-r);
return (sqrt(s));
}

double find_s(int k,double r)
{
int i;
double s;
if (k==0)
 s=-hl(r,1);
else
 s=hl(r,1);
for (i=2;i<=n;i++)
 s=s+hl(r,i);
return (s);
}

double judge(int k,double r)
{
double deg;
int i;
double b,c;
if (k==0)
 deg=2*PI-acos(1-(a[1]*a[1])/(2*r*r));
else
 deg=acos(1-(a[1]*a[1])/(2*r*r));
for (i=2;i<=n;i++)
 deg=deg+acos(1-(a[i]*a[i])/(2*r*r));
return (deg);
}

void solve()
{
int i,k;
double high,low,l;
double mid;
low=a[1]/2;high=1000000;
k=0;
if (judge(1,low)>2*PI)
 k=1;
else
 k=0;
while (high-low>0.00001)
 {
 mid=(high+low)/2;
 l=judge(k,mid);
 if (k==1)
  {
  if (l>PI*2)
   low=mid;
  else
   high=mid;
  }
 if (k==0)
  {
  if (l>PI*2)
   high=mid;
  else
   low=mid;
  }
 }
printf("%.2lf\n",find_s(k,mid));
}

main()
{
int i;
double sum;
init();
sum=0;
for (i=2;i<=n;i++)
 sum=sum+a[i];
if (sum<=a[1])
 printf("0.00\n");
else
solve();
return 0;
}

My program:

Program t1159;{$N+}

Const MaxN   = 100;
      Change = 180/Pi;
      OkW    = 360.0;
      Eps    = 1E-15;
      Eps2   = 1E-3;

Var   Block        : array[1..MaxN]of integer;
      N,i,sum,max  : integer;
      mx,t         : integer;
      left,rigth   : extended;
      middle       : extended;
      curW         : extended;
      ok           : boolean;

Function GetLW(R : extended;L : integer) : extended;
Var cosw,w,tgw  : extended;
 begin
  cosw:=(2*R*R-L*L)/(2*R*R);
  if cosw=0 then w:=90 else begin
    tgw:=sqrt(1-cosw*cosw)/cosw;
    w:=ArcTan(tgw)*Change;
    if w<0 then w:=180+w;
   end;
  GetLW:=w;
 end;

Function GetW(R : extended) : extended;
Var w     : extended;
    j     : integer;
 begin
  w:=0;
  for j:=1 to N do w:=w+GetLW(R,Block[j]);
  GetW:=w;
 end;

Function GetS(R : extended) : extended;
Var Ans,p,S  : extended;
    i        : integer;
 begin
  Ans:=0;
  for i:=1 to N do begin
    p:=(2*R+Block[i])/2;
    S:=sqrt(abs(p*(p-R)*(p-R)*(p-Block[i])));
    Ans:=Ans+S;
   end;
  GetS:=Ans;
 end;

Procedure WriteAns(R : extended);
 begin
  Writeln(GetS(R):0:2);
  Halt(0);
 end;

Procedure WriteAns2(R : extended);
Var S,p  : extended;
 begin
  p:=(2*R+Block[N+1])/2;
  S:=sqrt(p*(p-R)*(p-R)*(p-Block[N+1]));
  Writeln(GetS(R)-S:0:2);
  {Halt(0);}
 end;

begin
 Read(N);
 sum:=0;
 max:=0;
 for i:=1 to N do begin
   Read(Block[i]);
   sum:=sum+Block[i];
   if Block[i]>max then begin
    max:=Block[i];
    mx:=i;
   end;
  end;
 if mx<>N then begin
   t:=Block[mx];
   Block[mx]:=Block[N];
   Block[N]:=t;
  end;
 if max>=sum-max then begin
   writeln('0.00');
   halt(0);
  end;
 if max mod 2=0 then max:=max div 2 else max:=1+(max div 2);
 left:=max;
 rigth:=sum;
 While True do begin
   middle:=(left+rigth)/2;
   curW:=GetW(middle);
   if curW<OkW then rigth:=middle else left:=middle;
   if rigth-left<Eps then break;
  end;
 if abs(curW-OkW)<Eps2 then WriteAns(middle);
 N:=N-1;
 left:=max;
 rigth:=1E10;
 While True do begin
   middle:=(left+rigth)/2;
   curW:=GetW(middle);
   if curW>GetLW(middle,Block[N+1]) then rigth:=middle else
left:=middle;
   if rigth-left<Eps then break;
  end;
 writeans2(middle);
end.