Условие: Рабочие хотят огородить площадку для проведения строительных работ. Для этого они должны использовать K секций забора. Длина каждой секции забора не превышает 1000 метров. Необходимо определить, какую максимальную площадь можно огородить имеющимися секциями.
Технические условия: Первая строка входного файла input.txt содержит K (K <= 100). Вторая строка содержит K целых чисел - длины имеющихся секций забора. Выходной файл output.txt должен содержать одно число - максимальную площадь, которую можно огородить (с точностью 3 знака после запятой).
---------- cut ---------- Идея решения такая: максимальная площадь получится, если вписать многоугольник в окружность. Радиус находим двоичным поиском. Определяем, подходит радиус или нет, вычисляя сумму центральных углов и сравнивая с 2Pi. Предусмотрен случай, когда центр окружности лежит вне многоугольника (переменная-переключатель altmode). Возможно, точность надо подстроить (все эти 1e-16), потому что эти значения (и их соотношения) очень важны для корректной работы. ---------- cut ----------
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;
