Задача Maxtriangle. Цензура в геометричному світі! Багатокутники з кількістю сторін, що більша за 3, під забороною. У зв’язку з цим усі багатокутники намагаються перетворитись на трикутники (іноді вироджені). Роблять це вони у такий спосіб: поки кількість сторін не дорівнює 3, обираються дві суміжні сторони, що об’єднуються в одну, довжина якої дорівнює сумі довжин об’єднаних. Кожному багатокутнику цікаво, якою буде його максимально можлива площа після «трикутизацiї». Допоможіть їм у цьому!

Технічні умови. Програма  Maxtriangle  читає з пристрою стандартного введення число  N(3≤N≤7000) - кількість сторін опуклого багатокутника. В  цьому ж рядку слідує N натуральних чисел, кожне з яких не перевищує 105 - розміри сторін (сторони задаються у тій послідовності, у якій вони були в багатокутнику). Гарантується, що периметр багатокутника не перевищує 70000.  Програма виводить на пристрій стандартного виведення єдине дійсне число - максимальну площу багатокутника після «трикутизацiї». Відповідь буде зарахована, якщо відносна чи абсолютна похибка не перевищує 10−5 від відповіді журі.

Приклад

Введення

4 1 2 3 4

Виведення

4.472136

 

© LIKT 1998-2018