eolymp
bolt
Try our new interface for solving problems
Məsələlər

Магические палки

Магические палки

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Giriş verilənləri

Входные данные состоят из нескольких тестов. Каждый тест описывает магическую палку. Первая строка каждого теста задает количество n (1n500) отрезков в магической палке. Следующая строка содержит n целых чисел S_1, S_2, ..., S_n (1S_i1000) - длины отрезков в том же порядке, в котором они расположены на палке.

Последний тест завершается строкой, содержащей единственный ноль.

Çıxış verilənləri

Для каждого теста вывести его номер и максимально возможную площадь замкнутой области, которую можно получить, сгибая магическую палку в заданных местах. Допускаются ошибки округления не более 10^{-4}.

Формат выходных данных указан в примере.

Nümunə

Giriş verilənləri #1
4
1 2 3 4
0
Çıxış verilənləri #1
Case 1: 4.8989794820
Mənbə ICPC 2011 World Finals