A simple probability problem.

Equally-spaced parallel lines lie on an infinite plane. The separation between adjacent lines is D (D>0). Now considering a circle of diameter D. N points lie on or in the circle. It is guaranteed that any three points are not collinear. Between any two points there's a needle. Find the possibility that, if the circle is randomly (with equal probability on any position and direction) thrown onto the same plane described above (with the equally-spaced parallel lines of separation d), at least one needle crosses a line.

The first line contains a single integer T (1 <= T <= 100), the number of test cases.

For each set of input data, the first line gives two integers, N and D (N<=100), as described above. You can consider the center of the circle is default as the origin. Lastly N lines is followed, each containing two real numbers that representing the coordinate of a point lying within the circle.

Each output should occupy one line. Each line should start with "Case #i: ", followed by a real number round to four decimal places, the probability that at least one needle crosses one line.

2
2 2
-0.5 0
0.5 0
3 3
0 1
1 0
-1 0

Case #1: 0.3183
Case #2: 0.5123

BJTU

2014 Multi-University Training Contest 10