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