Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Оцените мой сайт
Всего ответов: 2669

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Пятница, 14.08.2020, 09:06
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Ограда
13.02.2012, 09:09

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

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

Примеры входных и выходных файлов:
Input.txt
3
3 4 5
Output.txt
6.000

Решение:
{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.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 566 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2020
/td>