시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB55517011842.909%

문제

넓은 초원이 있다. 민식이는 초원에 심은 풀이 이상한 사람들이 밟을 까봐 걱정한다. 따라서, 민식이는 초원에 삼각형 모양의 울타리를 치려고 한다.

민식이는 지하실에 N개의 울타리가 있다. 민식이는 3개의 울타리를 이용해서 삼각형 모양을 만든다. 삼각형의 각 변은 울타리 하나이다. 울타리는 붙이거나 쪼갤 수 없다.

민식이는 삼각형 넓이의 합을 최대로 하려고 한다.

입력

첫째 줄에 울타리의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄에 각 울타리의 길이가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 줄을 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1

7
3 4 5 6 7 8 9

예제 출력 1

36.754383146489694

예제 입력 2

4
1 2 4 8

예제 출력 2

0.0

예제 입력 3

4
7 4 4 4

예제 출력 3

6.928203230275509

예제 입력 4

16
21 72 15 55 16 44 54 63 69 35 75 69 76 70 50 81

예제 출력 4

7512.322360676162

힌트

$A \le B \le C$를 만족하는 $A$, $B$, $C$는 $A+B>C$를 만족할 때만 울타리를 만들 수 있다. 그리고, 그 때 넓이는 $\sqrt{p(p-A)(p-B)(p-C)}$이다. 여기서 $p=(A+B+C)/2$ 이다.

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: dotorya