Sunlight (Large)

A is getting married soon. He has enough money for a house, but one thing still bothers him: he wants a house that gets the sun for long enough. The sun rises in the east at 6 in the morning, moves along a semicircle, and sets in the west 12 hours later. The city is packed with buildings, so many houses lose the sun for part of the day behind another building. Work out how much of the city meets his condition.

In the picture the red segments are buildings, and the blue arc is the time range in which the house at the very bottom of the middle building sees the sun.

The city is a two dimensional plane and the ground is the x axis. The sun is a point that moves at constant speed along a semicircular path of radius $R$ centered at the origin. It rises at the east end $(R, 0)$ at 6:00 and sets at the west end $(-R, 0)$ at 18:00. Building $i$ is a vertical segment of width 0 from $(X_i, 0)$ to $(X_i, Y_i)$. No two buildings stand at the same position.

Building $i$ holds infinitely many houses spread evenly over the heights from $0$ to $Y_i$, and no two houses of one building sit at the same height. The house at height $y$ sees the sun at a given moment when the segment joining $(X_i, y)$ to the position of the sun at that moment does not meet another building. The building a house belongs to never blocks that house. The sunlight time of a house is the total time it sees the sun during the 12 hours.

Find the fraction of houses whose sunlight time is at least $H$ hours. Since the houses are spread evenly over height, that fraction equals the total length of the qualifying height ranges divided by the sum of the heights of all buildings.

The first line has the number of test cases $T$. Each test case has the following form.

N R H
X0 Y0
...
XN-1 YN-1

The first line of a test case has three integers: the number of buildings $N$, the radius $R$ of the semicircle the sun travels, and the minimum sunlight time $H$ that A has in mind. Each of the next $N$ lines has two integers describing one building. $X_i$ is the x coordinate of the building relative to the center of the semicircle, and $Y_i$ is its height.

Limits

• $1 \le T \le 100$
• $1 \le N \le 200$
• $100 \le R \le 1000$
• $1 \le H \le 12$
• $Y_i > 0$
• $X_i^2 + Y_i^2 < R^2$
• $X_i \ne X_j$ for $i \ne j$
• Every number in the input is an integer.

For each test case print one line of the form "Case #x: y". Here $x$ is the test case number starting from 1, and $y$ is the fraction of houses that meet the condition. Print $y$ rounded to exactly seven digits after the decimal point.