Problem B

Probability Through experiment

Time Limit: 2 seconds

Mathematicians have often solved problems by just doing some simulation or experiments. For example, the value of pi (p) can be approximately determined by randomly plotting points in a square that inscribes a circle. Because if the square is a 250x250 square, then its area is 62500 and the area of the inscribed circle is pi*125²=15625pi. As the points are plotted randomly, so it can be assumed that number of points inside the circle and total number points plotted in the square is proportional to their respective area. So, in this way, the value of pi can approximately be determined by counting how many points are inside the circle (Figure 1). The value of pi can even be determined using a more sophisticated experiment like the Buffon’s needle experiment (Figure 2).

The two experiments mentioned above to approximately determine the value of pi could be simulated by writing a computer program very easily. It would have been nice to do this sort of experiment a lot of time (Say 1 billion billion) and get an almost perfect result but for lack of time we cannot do that in real life. In this problem, you will have to write a program that will help Professor Wu to perform a similar sort of experiment but this program may not be that straightforward.

Professor Neal Wu is trying to solve a classic problem using simulation: If three points are randomly plotted on the boundary of a circle, then what is the probability that they will be the three vertex of an acute triangle? Of course, this problem can be solved analytically and the result he gets is 0.25. Now, he wants to verify this result through an experiment. The result can be found approximately by plotting three random points on a circle billions of times and counting how many times these three points form an acute triangle. The beauty of such an experiment (as mentioned above) is that if we increase the number of trials, the result will become even more accurate. But if Dr. Wu wants to repeat this process 1000 billion times, it will take 2 hours of time and if he wants to repeat it a billion billion times, it may take more than 200 years. Dr. Wu has discovered that this process can be sped up by using a different approach – generate n random points on the boundary of a circle and they form  triangles as vertices. How many of these triangles are acute triangles? If the number of acute triangle is M and let N = , then the desired probability is . So, given the n points on the boundary, you have to assist Dr. Wu by writing a very efficient program to find the number of acute triangles.

Input

The input file contains around 40 test cases. But most of the cases are not extreme, so the size of the input file is around 3 MB. The description of each test case is given below:

Each case starts with two positive integers n (0 < n ≤ 20000) and r (0 < r ≤ 500). Here, n is the total of points on the circle boundary and r is the radius of the circle. The center of the circle is always at the origin (0,0). Each of the next N lines denotes the location of one point on the boundary of the circle. Each point is P, denoted by a floating-point number θ (0.000 ≤ θ < 360.000). This θ is actually the angle (expressed in degree) the point P creates at the center of the circle with the positive direction of x-axis. So the Cartesian coordinate of P is ( r*cos(θ), r*sin(θ)). Value of θ will always have exactly three digits after the decimal point. No two points will be at the same location.       

A line containing two zeroes terminates the input. This line should not be processed.

Output

Each test case produces one line of output. This line contains the serial of output followed by an integer. This integer denotes how many of the   triangles formed by these n points are actually acute triangles.

/* 20000 points generated on the boundary of a circle can actually create 20000*19999*19998/6 ~1333 billion triangles. So, of experiment for 1333 billions can be done in, say, 0.5 second. Then experiments with 1 billion billion triangles can be done in around 100 hours only (In contrast to 200 years mentioned earlier) just by repeating this experiment. Also, if we put 1817120 points on the boundary of the circle, around 1 billion billion triangles are created, and the number of acute triangles within this large number of triangles can be computed within 5 minutes. */

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int x[20005];
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, r, i, j, a, b;
    int cases = 0;
    while(scanf("%d %d", &n, &r) == 2) {
        if(n == 0)  break;
        for(i = 0; i < n; i++) {
            ReadInt(&a);
            ReadInt(&b);
            x[i] = a*1000+b;
        }
        sort(x, x+n);
        long long tot = 0, t1, t2, normal = 0, ans;
        ans = (long long)n*(n-1)*(n-2)/6;
        queue<int> Q;
        for(i = 0, j = 0; i < n; i++) {
            if(x[i] >= 180000)  break;
            while(j < n && x[j] <= x[i]+180000)
                Q.push(x[j]), j++;
            while(!Q.empty() && Q.front() <= x[i])  Q.pop();
            t1 = Q.size();
            t2 = n-1-t1;
            if(j > 0 && x[j-1] == x[i]+180000)
                t1--, normal += t1+t2;
            tot += t1*(t1-1)/2;
            tot += t2*(t2-1)/2;
        }
        for(i = 0; i < n; i++) {
            x[i] += 180000;
            if(x[i] >= 360000)  x[i] -= 360000;
        }
        sort(x, x+n);
        while(!Q.empty())   Q.pop();
        for(i = 0, j = 0; i < n; i++) {
            if(x[i] >= 180000)  break;
            while(j < n && x[j] <= x[i]+180000)
                Q.push(x[j]), j++;
            while(!Q.empty() && Q.front() <= x[i])  Q.pop();
            t1 = Q.size();
            t2 = n-1-t1;
            if(j > 0 && x[j-1] == x[i]+180000)
                t1--, normal += t1+t2;
            tot += t1*(t1-1)/2;
            tot += t2*(t2-1)/2;
        }
        printf("Case %d: %lld\n", ++cases, ans-tot/2-normal/2);
    }
    return 0;
}