cho.sh안테나 수리 (Small)
주어진 길이의 막대 K개를 한 점 주위에 같은 간격으로 배치해 이웃 삼각형 넓이 합을 최대로 합니다.
보통4완전 탐색기하수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제 설명
예제6
문제
탐험가 파스칼이 고대 문명이 남긴 외계인 통신 장치를 발견하고 사용법을 알아냈다. 이 장치의 안테나는 K 개의 소자로 이루어진다. 소자는 특수 물질로 만든 곧은 막대이고, 한쪽 끝을 플러스 극, 반대쪽 끝을 마이너스 극이라고 한다. 소자에는 1번부터 K 번까지 번호가 붙어 있다.
안테나가 동작하려면 다음 네 조건을 모두 만족하도록 조립해야 한다.
- 모든 소자가 같은 평면 위에 있다.
- 모든 소자의 플러스 극이 한 점에 모인다. 이 점을 접속점이라고 한다.
- 소자끼리 만나는 곳은 접속점뿐이다.
- 이웃한 두 소자가 이루는 각은 모두 360/K 도이다.
각의 합이 정확히 한 바퀴이므로 소자는 접속점을 중심으로 고리 모양으로 늘어서고, 이웃한 소자 쌍은 정확히 K 개다. 한 쌍을 골라 두 소자의 마이너스 극 두 점과 접속점을 잇는 삼각형을 만들면, 이런 삼각형 K 개의 넓이를 모두 더한 값이 안테나의 강도다.
강도가 가장 커지도록 배치했을 때의 강도를 구하라.
소자의 굵기는 무시한다. 소자를 자를 수 없고, 여러 소자를 이어서 한 개의 소자로 쓸 수도 없다.
입력
첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 T 가 주어진다. 각 테스트 케이스는 다음 형식이다.
K
E1 E2 ... EK
K 는 소자의 개수다. Ei 는 양의 정수로, i 번 소자의 길이를 나타낸다.
제약 조건
- 1≤T≤100
- 3≤K≤5
- 1≤Ei≤1000
출력
각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.
Case #X: P
X 는 1부터 시작하는 테스트 케이스 번호이고, P 는 최대 강도다. P 는 소수점 아래 여섯 자리까지 반올림해서, 자리를 채워 출력한다. 예를 들어 강도가 2이면 2.000000 으로 쓴다.
Loading...