레이팅 미적용마법은 고대의 모든 민족에게 신적 힘의 도움을 얻어 내는 기술로 받아들여졌다. 잘 알려진(we\(ll-kn\)own) 이야기에서, 한 무리의 마법사들이 지팡이를 바닥에 던지자 지팡이가 마법처럼 살아 있는 뱀으로 변한 것처럼 보였다. 이에 맞서 다른 한 사람이 자신의 지팡이를 바닥에 던지자 그것이 뱀으로 변해 마법사들의 뱀을 모두 삼켜 버렸다! 이 문제에 필요한 유일한 마법은 문제의 풀이뿐이다. 당신에게는 여러 개의 곧은 조각으로 이루어진 마법 지팡이가 주어지며, 조각 사이의 관절 덕분에 지팡이를 접을 수 있다. 조각의 길이와 접는 방법에 따라 지팡이의 조각들을 배열해 여러 다각형을 만들 수 있다. 각 조각을 최대 하나의 다각형에만 사용하여, 지팡이를 접어 만든 다각형들이 둘러쌀 수 있는 넓이의 최댓값을 구해야 한다. 조각들은 끝점에서만 닿을 수 있다. 예를 들어 아래 왼쪽 그림의 지팡이는 조각 다섯 개와 관절 네 개로 되어 있다. 이를 접으면 오른쪽 그림과 같은 다각형을 만들 수 있다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 마법 지팡이 하나를 설명한다. 각 테스트 케이스의 첫 줄에는 마법 지팡이의 조각 수를 나타내는 정수 \(n\) (\(1 \le n \le 500\))이 주어진다. 다음 줄에는 지팡이에 나타나는 순서대로 조각의 길이를 나타내는 \(n\)개의 정수 \(S\)1, S2, . . . , S\(n\) (\(1 \le Si \le 1000\))이 주어진다. 마지막 테스트 케이스 다음에는 0 하나가 있는 줄이 주어진다.
각 케이스마다 케이스 번호와 함께, 주어진 지점에서 마법 지팡이를 접어 얻을 수 있는, 둘러싸인 넓이의 최대 총합을 출력한다. 절대 또는 상대 오차가 \(10^{−}^{4}\) 이내인 답이 정답으로 인정된다. 샘플 출력의 형식을 따른다.
4
1 2 3 4
8
3 4 5 33 3 4 3 5
0
ICPC 2011 World Finals Problem G: Magic Sticks
Case 1: 4.898979
Case 2: 19.311