Модуль: Тернарный поиск


Задача

9 /10


Вложенный тернарный поиск: футбольные ворота

Теория Нажмите, чтобы прочитать/скрыть


Вложенный тернарный поиск можно применить, когда у нас оптимизационная задача с двумя неизвестными. Данная задача как раз про это.

Очевидно, что ворота будут в форме четырехугольника, с прямым углом в основании, тогда нам остается подобрать 2 угла (α и β) таким образом, чтобы площадь ворот была максимальной. Для этого создадим тернарный поиск, который даст нам 2 угла (α1и α2), и для каждого из этих α мы запустим еще один тернарный поиск, который подберет нам такие β, при которых площадь будет максимальной.

Подробнее можно прочитать здесь

Задача

Соня, в отличие от многих студентов мат-меха, спортивна не только в программировании. В один прекрасный день она отправилась поиграть в футбол с друзьями. К сожалению, нигде поблизости не оказалось специально оборудованного футбольного поля, только высокая берёза одиноко красовалась в глубине двора. Покопавшись дома в кладовке, Соня нашла две палки и решила соорудить футбольные ворота из палок и берёзы. Конечно, берёза будет использована как одна из боковых стоек ворот. Осталось сделать из двух палок вторую стойку и перекладину.
Соня, конечно, хочет забить как можно больше голов. Поэтому она решила сделать ворота максимальной площади. Стандартные футбольные ворота имеют прямоугольную форму, но Соня — человек креативный, и она считает, что ворота могут иметь форму произвольного четырёхугольника.

Можно считать, что берёза является отрезком прямой и растёт строго перпендикулярно земле.
 
Входные данные
В единственной строке записаны целые числа a, b  — длины палок (\(1 <= a, b <= 10 000\)). Известно, что суммарная длина палок строго меньше высоты берёзы.

Выходные данные
Выведите максимальную площадь ворот, которые можно соорудить из палок и берёзы. Ответ следует вывести с точностью не менее шести знаков после десятичной точки.

 

Примеры
Входные данные Выходные данные
1 2 2 4.828427125
Источник: Уральская региональная командная олимпиада по программированию 2011

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6410
Python22
Комментарий учителя