Задача Maxtriangle. Цензура в геометричному світі! Багатокутники з кількістю сторін, що більша за 3, під забороною. У зв’язку з цим усі багатокутники намагаються перетворитись на трикутники (іноді вироджені). Роблять це вони у такий спосіб: поки кількість сторін не дорівнює 3, обираються дві суміжні сторони, що об’єднуються в одну, довжина якої дорівнює сумі довжин об’єднаних. Кожному багатокутнику цікаво, якою буде його максимально можлива площа після «трикутизацiї». Допоможіть їм у цьому!
Технічні умови. Програма Maxtriangle читає з пристрою стандартного введення число N(3≤N≤7000) - кількість сторін опуклого багатокутника. В цьому ж рядку слідує N натуральних чисел, кожне з яких не перевищує 105 - розміри сторін (сторони задаються у тій послідовності, у якій вони були в багатокутнику). Гарантується, що периметр багатокутника не перевищує 70000. Програма виводить на пристрій стандартного виведення єдине дійсне число - максимальну площу багатокутника після «трикутизацiї». Відповідь буде зарахована, якщо відносна чи абсолютна похибка не перевищує 10−5 від відповіді журі.
| Приклад | |
|
Введення 4 1 2 3 4 |
Виведення 4.472136 |