405719: GYM102055 F Cones

Here is a simple geometry problem: calculate the volume of union of identical cones. These cones are located on the $$$z = 0$$$ plane. A cone at $$$(x_0, y_0, 0)$$$ is defined as $$$\{(x,y,z) \mid 0 \le z \le 1 - \sqrt{(x-x_0)^2+(y-y_0)^2}\}$$$. Given the locations of cones, $$$(x_k, y_k)$$$, calculate the volume of the union of these cones.

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 100$$$). $$$T$$$ test cases follow.

Each case starts with a line of a single integer $$$N$$$ ($$$1 \le N \le 1000$$$), indicating the number of cones, then $$$N$$$ lines follow. Each line contains two real numbers $$$x_k$$$ and $$$y_k$$$ with 4 digits after decimal point indicating the location of the $$$k^{th}$$$ cone, where $$$-20.0\le x_k, y_k \le 20.0$$$, and no two points will be coincided.

For at least $$$90\%$$$ test cases, it is guaranteed that $$$N \leq 300$$$.

For each test case, output one line containing "Case x: y", where x is the test case number (starting from $$$1$$$) and y is the volume of the union of the cones. Your answer will be considered correct if it is within an absolute or relative error of $$$10^{-6}$$$ of the correct answer.

4
1
0.0000 0.0000
2
0.0000 0.0000
1.0000 0.0000
3
-4.1850 0.8550
3.8150 4.0400
2.1300 -2.6700
5
5.6422 7.8467
-5.7704 9.1233
-1.2843 5.2843
3.8242 -2.2140
-4.6870 1.8571

Case 1: 1.047197551196598
Case 2: 1.863867179374688
Case 3: 3.141592653589793
Case 4: 5.235987755982988