Probability Through Experiment

Mathematicians have long estimated quantities by running simple simulations or physical experiments. For example, the value of $\pi$ can be approximated by scattering random points inside a square that circumscribes a circle. If the square measures $250 \times 250$, its area is $62500$, and the inscribed circle (radius $125$) has area $\pi \cdot 125^2 = 15625\pi$. Because the points are placed uniformly at random, the fraction that land inside the circle is proportional to the ratio of the two areas, so counting how many points fall inside the circle yields an estimate of $\pi$ (Figure 1). The same constant can also be estimated with a more elaborate setup such as Buffon's needle experiment (Figure 2).

Figure 1: Approximating pi by counting the points inside the circle	Figure 2: Buffon's needle experiment	Figure 3: A circle with points given on its boundary

Both experiments are easy to simulate on a computer. Ideally we would repeat such an experiment an enormous number of times to obtain an almost perfect result, but doing so directly is far too slow.

Professor Neal Wu wants to verify a classic result by simulation: if three points are chosen uniformly at random on the boundary of a circle, what is the probability that they form an acute triangle? The exact answer is known to be $0.25$, and he would like to confirm it experimentally. A naive simulation places three random points on the circle billions of times and counts how often they form an acute triangle; the more trials, the more accurate the estimate, but repeating the process a huge number of times could take centuries.

Professor Wu speeds this up with a different idea: place $n$ random points on the boundary of the circle at once. These $n$ points define $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$ triangles. If $M$ of them are acute and $N = \frac{n(n-1)(n-2)}{6}$, then the estimated probability is $M / N$.

Given the $n$ points on the boundary, write an efficient program that reports $M$, the number of acute triangles among all $\binom{n}{3}$ triangles.

The input contains several test cases (around 40).

Each test case begins with a line containing two positive integers $n$ and $r$ ($0 < n \le 20000$, $0 < r \le 500$), where $n$ is the number of points on the circle and $r$ is its radius. The circle is always centered at the origin $(0, 0)$.

Each of the next $n$ lines contains one real number $\theta$ ($0.000 \le \theta < 360.000$, always with exactly three digits after the decimal point). It is the angle, in degrees, that the point makes at the center with the positive $x$-axis, so the point's coordinates are $(r\cos\theta, r\sin\theta)$. No two points coincide.

A line containing two zeros terminates the input and must not be processed.

For each test case, print one line in the form Case X: M, where $X$ is the test case number starting from $1$ and $M$ is the number of acute triangles among the $\binom{n}{3}$ triangles formed by the given points.