망원경

Dr. Extreme은 극도로 먼 곳에서 일어나는 극도로 흥미로운 현상을 조사하기 위해 극도로 정밀한 망원경을 실험적으로 만들었다. 그렇게 먼 곳의 현상을 조사할 만큼 망원경을 정밀하게 만들려면 아주 작은 왜곡조차 허용되지 않는다. 하지만 그는 망원경을 통과하는 자속의 저주파 진동에 영향을 받는 내부 기체의 영향을 잊고 있었다. 망원경의 원통은 저주파 진동에 영향을 받지 않지만 내부 기체는 영향을 받는다.

망원경의 단면은 완전한 원을 이룬다. (안쪽) 원둘레를 따라 극도로 가는 선을 감아 코일을 만들면 자속의 시간적 변화량(의 평균 수직 성분)을 측정할 수 있는데, 이 측정은 그 영향을 추정하는 데 유용할 것이다. 그러나 선을 고정할 수 있는 원둘레 위의 점은 제한적이고, 선을 고정할 특수 클립의 개수도 제한적이다. 그는 가장 높은 감도를 얻기 위해 원둘레 위에서 신중히 고른 점들 사이로 선을 이어 가장 넓은 면적의 다각형 코일을 만들고자 한다.

여러분의 임무는 반지름이 1인 원둘레 위에 주어진 n개의 점 중에서 꼭짓점을 고른 모든 m-다각형(꼭짓점이 정확히 m개인 다각형)의 최대 면적을 출력하는 프로그램을 작성하는 것이다. n = 4, m = 3인 경우의 예가 아래에 나와 있다.

위 그림에서 “p1 = 0.0”과 같은 식은 주어진 n개 점의 위치를 나타내고, m-다각형 위의 “1.000000”과 같은 소수는 m-다각형의 면적을 나타낸다.

매개변수 pi는 원둘레 위 i번째 주어진 점의 위치를 나타낸다(1 ≤ i ≤ n). 원둘레 위 점의 위치 p는 0 ≤ p < 1 범위이고, 이는 0부터 2π 라디안까지의 회전각 범위에 대응한다. 즉, p에 있는 점에서 0에 있는 점까지의 회전각은 2πp 라디안이다. (π는 원주율 3.14159265358979323846…이다.)

AB = AC = 1이고 내각 BAC가 α 라디안(0 < α < π)인 이등변삼각형 ABC의 면적이 (1/2)·sin α이고, 반지름이 1인 원에 내접하는 다각형의 면적이 π보다 작다는 사실을 이용해도 된다.

입력은 여러 개의 부분 문제로 이루어지고, 입력의 끝을 나타내는 두 개의 0이 있는 줄이 뒤따른다. 각 부분 문제는 다음 형식으로 주어진다.

n m
p1 p2 ··· pn

n은 원둘레 위 점의 개수이다(3 ≤ n ≤ 40). m은 m-다각형을 이룰 꼭짓점의 개수이다(3 ≤ m ≤ n). n개 점의 위치 p1, p2, ..., pn은 소수로 주어지고, 공백 문자나 줄바꿈으로 구분된다. 또한 0 ≤ p1 < p2 < ··· < pn < 1이라고 가정해도 된다.

각 부분 문제마다 최대 면적을 한 줄에 하나씩 출력한다. 출력하는 각 값의 오차는 0.000001보다 클 수 없고, 소수점 아래 6자리까지 출력한다.