В
рамках проекта Sapisoft открывается новый проект -
"Задача в неделю". Руководитель - Алексеев
А.В. Форма для подписки на рассылку - в конце
номера. Подробная информация - в разделах
"Задачи" и "Рассылки" на нашем сайте.
В этом выпуске позвольте представить вам
ещё одну задачу, любезно предоставленную HellMan'ом
[alexec@polarcom.ru].
Ограда
(3 уровень)
Условие:
Рабочие хотят огородить площадку для
проведения строительных работ. Для этого они
должны использовать K секций забора. Длина каждой
секции забора не превышает 1000 метров. Необходимо
определить, какую максимальную площадь можно
огородить имеющимися секциями.
Технические
условия: Первая строка
входного файла input.txt содержит K (K <= 100). Вторая
строка содержит K целых чисел - длины имеющихся
секций забора. Выходной файл output.txt должен
содержать одно число - максимальную площадь,
которую можно огородить (с точностью 3 знака
после запятой).
Примеры
файлов:
Input.txt
Output.txt
3
3 4 5
6.000
Решение:(by
HellMan [alexec@polarcom.ru])
---------- 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;
