Задача Maxtriangle. Цензура в геометрическом мире! Многоугольники с количеством сторон, большим 3, под запретом. В связи с этим все многоугольники пытаются превратиться в треугольники (иногда вырожденные). Делают это они таким способом: пока количество сторон не равно 3, выбираются две смежных стороны, которые объединяются в одну, длина которой равняется сумме длин объединенных. Каждому многоугольнику интересно, какой будет его максимально возможная площадь после "треугольнизации". Помогите им в этом!  

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

Пример

Ввод

4 1 2 3 4

Вывод

4.472136

 

© LIKT 1998-2018