Cleaning the Hallway

$N$ people clean the floor with $N$ vacuum cleaners. It looks like they can clean the whole floor, but they cannot. A cleaner runs only while it is plugged into an outlet in the floor, and the wire has a fixed length.

If the wire of a cleaner is $D$ long, the person using that cleaner can move at most $D$ away from the outlet. The wire is faulty, so the moment it goes even slightly loose, meaning the person comes closer than $D$ to the outlet, the cleaner loses power. The person can therefore stand only at distance exactly $D$ from the outlet. The handle is heavy as well, so the person cannot push the cleaner head farther than $d$ from where they stand.

In short, one cleaner cleans every point of the floor at distance $d$ or less from a person standing at distance exactly $D$ from the outlet.

For each cleaner you are given $D$, $d$, and the coordinate of the outlet it is plugged into. Find the area of the floor that can be cleaned with this arrangement. Several people may clean the same spot, so the answer is the area of the union, not the sum of the areas each of them cleans.

The first line has the number of test cases $T$. ($1 \le T \le 30$)

Each test case has the following form.

• The first line has the number of cleaners $N$. ($1 \le N \le 500$)
• Each of the next $N$ lines has four integers $x$, $y$, $D$, $d$ separated by one space, describing one cleaner. $(x, y)$ is the coordinate of the outlet, $D$ is the wire length, and $d$ is the distance between the person and the cleaner head. ($|x|, |y| \le 1000$, $0 < D, d \le 200$)

For each test case print one line in the form Case x: A. Here $x$ is the test case number starting from 1, and $A$ is the cleanable area rounded to two decimal places.

The exact area always differs by more than $10^{-5}$ from every value of the form $0.005 + 0.01k$ ($k$ an integer), so the rounded value is determined uniquely.

The first test case has a single cleaner. The outlet sits at $(0, 0)$ with $D = 10$ and $d = 1$, so the person walks along the circle of radius 10 centered at $(0, 0)$. The cleaner reaches every point at distance 1 or less from the person, so the cleaned region is the ring between the two circles centered at $(0, 0)$ with radii 9 and 11. Its area is $\pi \times (11^2 - 9^2) = 125.6637\ldots$, printed as 125.66.

The second test case has two cleaners. The first one is plugged into the outlet at $(0, 0)$ and cleans the ring between radii 6 and 8. The second one is plugged into the outlet at $(13, 0)$ and cleans the ring between radii 9 and 11. The two rings overlap, so the area of the union is smaller than the sum of the two ring areas.