Тернарный поиск




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

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

http://kesh.kz/blog/%D0%B2%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9-%D1%82%D0%B5%D1%80%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9-%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D1%81-%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D1%8B%D0%BC-%D1%81/

Task
Time limit: 1000 ms,
Memory limit: 256 Mb

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

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

Результат
Выведите максимальную площадь ворот, которые можно соорудить из палок и берёзы. Ответ следует вывести с точностью не менее шести знаков после десятичной точки.
 
Ввод Вывод
2 2 4.828427125
Источник: Уральская региональная командная олимпиада по программированию 2011

 

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!
Attach the program source file:
or enter the source code in the language:

Rules for designing programs and a list of errors during automatic task verification
           

Results: