삼각형 만들기
시간 제한2초메모리 제한128 MB
최대 40개의 막대를 세 그룹으로 모두 나누어 각 그룹의 길이 합이 삼각형의 세 변을 이루도록 하고, 헤론의 공식으로 계산한 넓이가 최대가 되는 값을 구합니다.
문제
N(3 ≤ N ≤ 40)개의 막대가 주어진다. 막대들의 길이는 서로 같을 수도 있고 다를 수도 있다. 모든 막대를 하나도 빠뜨리지 않고 세 그룹으로 나눈 뒤, 각 그룹의 막대를 일렬로 이어 붙여 삼각형의 한 변으로 사용하려고 한다.
이렇게 만들 수 있는 삼각형 중 넓이가 가장 큰 삼각형의 넓이를 구하시오.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 막대의 길이 L(1 ≤ L ≤ 40)이 한 줄에 하나씩 주어진다.
출력
만들 수 있는 삼각형의 최대 넓이에 100을 곱한 뒤 소수점 이하를 버린 정수를 출력한다. 삼각형을 만들 수 없다면 -1을 출력한다.
힌트
삼각형의 세 변의 길이가 a, b, c일 때 s = (a + b + c) / 2 라고 하면, 넓이의 제곱은 s × (s - a) × (s - b) × (s - c)이다.