실험을 통한 확률

수학자들은 오래전부터 간단한 시뮬레이션이나 실험으로 여러 값을 근사해 왔습니다. 예를 들어 원에 외접하는 정사각형 안에 점을 무작위로 찍으면 원주율 $\pi$의 값을 근사할 수 있습니다. 정사각형의 한 변이 $250$이면 넓이는 $62500$이고, 내접하는 원(반지름 $125$)의 넓이는 $\pi \cdot 125^2 = 15625\pi$입니다. 점을 균일하게 무작위로 찍으므로 원 안에 들어간 점의 개수는 두 넓이의 비에 비례합니다. 따라서 원 안에 들어간 점의 수를 세면 $\pi$를 근사할 수 있습니다(그림 1). 뷔퐁의 바늘 실험처럼 더 정교한 방법으로도 같은 값을 구할 수 있습니다(그림 2).

그림 1: 원 안의 점 개수를 세어 원주율을 근사	그림 2: 뷔퐁의 바늘 실험	그림 3: 경계 위에 점이 주어진 원

두 실험 모두 컴퓨터로 쉽게 시뮬레이션할 수 있습니다. 이상적으로는 이런 실험을 아주 많이 반복하면 거의 완벽한 결과를 얻을 수 있지만, 실제로 그렇게 하기에는 시간이 너무 오래 걸립니다.

Neal Wu 교수는 고전적인 결과를 시뮬레이션으로 검증하려고 합니다. 원의 경계 위에서 세 점을 균일하게 무작위로 고르면, 그 세 점이 예각삼각형을 이룰 확률은 얼마일까요? 이 값은 정확히 $0.25$로 알려져 있으며, 교수는 이를 실험으로 확인하고자 합니다. 단순한 방법은 원 위에 세 점을 무작위로 아주 여러 번 찍어 예각삼각형이 되는 횟수를 세는 것입니다. 시행 횟수가 많을수록 추정값은 정확해지지만, 이 과정을 아주 많이 반복하려면 수백 년이 걸릴 수도 있습니다.

Wu 교수는 다른 방법으로 이 과정을 빠르게 만듭니다. 원의 경계 위에 한 번에 $n$개의 점을 찍는 것입니다. 이 $n$개의 점은 $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$개의 삼각형을 만듭니다. 그중 예각삼각형이 $M$개이고 $N = \frac{n(n-1)(n-2)}{6}$이라 하면, 구하려는 확률은 $M / N$입니다.

경계 위의 $n$개의 점이 주어질 때, 이 점들로 만들 수 있는 $\binom{n}{3}$개의 삼각형 중 예각삼각형의 개수 $M$을 구하는 효율적인 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다(약 40개).

각 테스트 케이스는 두 양의 정수 $n$과 $r$($0 < n \le 20000$, $0 < r \le 500$)이 주어지는 줄로 시작합니다. $n$은 원 위의 점의 개수, $r$은 원의 반지름이며, 원의 중심은 항상 원점 $(0, 0)$입니다.

이어지는 $n$개의 줄에는 각각 실수 $\theta$($0.000 \le \theta < 360.000$, 소수점 아래 항상 세 자리)가 주어집니다. 이는 해당 점이 중심에서 양의 $x$축과 이루는 각도(도 단위)이므로, 점의 좌표는 $(r\cos\theta, r\sin\theta)$입니다. 같은 위치에 있는 점은 없습니다.

두 개의 $0$으로 이루어진 줄이 입력의 끝을 나타내며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 한 줄씩 Case X: M 형식으로 출력합니다. $X$는 $1$부터 시작하는 테스트 케이스 번호이고, $M$은 주어진 점들로 만들어지는 $\binom{n}{3}$개의 삼각형 중 예각삼각형의 개수입니다.