Ограда (5 уровень)

Условие:
Рабочие хотят огородить площадку для проведения строительных работ. Для этого они должны использовать K секций забора. Длина каждой секции забора не превышает 1000 метров. Необходимо определить, какую максимальную площадь можно огородить имеющимися секциями.

Технические условия:
Первая строка входного файла input.txt содержит K (K <= 100). Вторая строка содержит K целых чисел - длины имеющихся секций забора. Выходной файл output.txt должен содержать одно число - максимальную площадь, которую можно огородить (с точностью 3 знака после запятой).

Примеры файлов:

Решение: (by HellMan [alexec@polarcom.ru])

---------- cut ----------
Идея решения такая: максимальная площадь получится, если вписать многоугольник в окружность. Радиус находим двоичным поиском. Определяем, подходит радиус или нет, вычисляя сумму центральных углов и сравнивая с 2Pi.
Предусмотрен случай, когда центр окружности лежит вне многоугольника (переменная-переключатель altmode). Возможно, точность надо подстроить (все эти 1e-16), потому что эти значения (и их соотношения) очень важны для корректной работы.
---------- cut ----------

{$A-,B-,D+,E-,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X-,Y+}
{$M 16384,0,655360}

program Fence;

type
  returnValue = -1..1;

const
  pi2: extended = 6.2831853071795865;

var
  f: text;
  k, i: byte;
  a: array[1..100] of word;
  max, sum: longint;
  ml, mr, r, ar: extended;
  res: returnvalue;
  done: boolean;

label
  OUT;

function test(const r: extended; const altmode: boolean): returnvalue;
var ang, max, sum: extended;
    i: byte;
begin
  max := 0;
  sum := 0;
  for i := 1 to k do
  begin
    ang := sqrt(sqr(r) - 0.25 * sqr(a[i]));
    if abs(ang) <= 1e-25 then
    ang := 0.7853981633974483
      else
        ang := 2 * arctan(0.5 * a[i] / ang);
    sum := sum + ang;
    if max < ang then
    max := ang;
  end;
  if not altmode then
  begin
    if abs(sum - pi2) < 1e-7 then
    begin
      test := 0;
      exit;
    end;
  end;
  if altmode then
  begin
    sum := sum + pi2 - 2 * max;
    if abs(sum - pi2) < 1e-7 then
    begin
      test := 0;
      exit;
    end;
  end;
  if sum > pi2 then
  test := 1
    else
     test := -1;
end;

function area(const r: extended; const altmode: boolean): extended;
var i: byte;
    p, ar: extended;
begin
  ar := 0;
  for i := 1 to k do
  begin
    p := r + 0.5 * a[i];
    ar := ar + (p - r) * sqrt(p * (p - a[i]));
  end;
  if altmode then
  begin
    p := r + 0.5 * max;
    ar := ar - 2 * (p - r) * sqrt(p * (p - max));
  end;
  area := ar;
end;

begin
  assign(f, 'input.txt');
  reset(f);
  readln(f, k);
  max := 0;
  sum := 0;
  for i := 1 to k do
  begin
    read(f, a[i]);
    inc(sum, a[i]);
    if a[i] > max then
    max := a[i];
  end;
  close(f);
  if max >= sum / 2 then
   begin
    ar := 0;
    goto OUT;
  end;

  ml := max / 2;
  mr := sum / 2;
  done := false;

  while mr - ml > 1e-16 do
  begin
    r := (ml + mr) / 2;
    res := test(r, false);
    if res = 0 then
    begin
      done := true;
      ar := area(r, false);
      break;
    end;
    if res = -1 then
    mr := r
      else
        ml := r;
  end;

  ml := max / 2;
  mr := sum / 2;
  while not done do
  begin
    if mr - ml < 1e-7 then
    begin
      ml := mr;
      mr := ml * 4;
    end;
    r := (ml + mr) / 2;
    res := test(r, true);
    if res = 0 then
    begin
      done := true;
      ar := area(r, true);
      break;
    end
     else
     if res = 1 then
     mr := r
       else
        ml := r;
  end;

  OUT:
  assign(f, 'output.txt');
  rewrite(f);
  writeln(f, ar:5:3);
  close(f);
end.