Aris is playing the classic game, Angry Birds!
Because Aris has been playing for too long, Yuuka confiscated Aris's game console and demanded that Aris complete today's math homework before getting it back.
However, Sensei did not assign any math homework to Aris today, so Yuuka had to come up with a problem for Aris to solve.
Consider the game field of Angry Birds as a three-dimensional Euclidean space, and the bird as a sphere with radius $$$ R_3 $$$. Establish a spatial Cartesian coordinate system $$$ O-xyz $$$, such that the trajectory of the bird's center lies in the horizontal plane $$$ z=0 $$$.
It is known that the trajectory of the bird's center is a closed polyline, consisting of $$$ n $$$ segments connected end to end. The connection points are $$$ n $$$ points: $$$ (x_1, y_1, 0), (x_2, y_2, 0), \cdots, (x_n, y_n, 0) $$$. The $$$ i $$$-th segment has endpoints $$$ (x_i, y_i, 0) $$$ and $$$ (x_{i \bmod n + 1}, y_{i \bmod n + 1}, 0) $$$. However, due to sensor errors, the actual $$$ n $$$ points may deviate from $$$ (x_i, y_i, 0) $$$ by a distance not exceeding $$$ R_2 $$$ (the sensor deviation $$$ R_2 $$$ is the same for all points). That is, the actual $$$ i $$$-th point $$$ (x'_i, y'_i, 0) $$$ can be anywhere within the circle (which is still contained in the plane $$$ z=0 $$$) centered at $$$ (x_i, y_i, 0) $$$ with radius $$$ R_2 $$$.
Let $$$ S $$$ be the set of all points that the entire bird may pass through, i.e., points in 3D space whose distance to the bird's center trajectory is at most $$$ R_3 $$$. Yuuka requires Aris to compute the volume of the convex hull of $$$ S $$$.
Convex hull: The convex hull of a point set $$$ S $$$ is defined as the smallest set $$$ T $$$ such that for any two points in $$$ S $$$, all points on the line segment between them are contained in $$$ T $$$.
The first line contains a positive integer $$$ T $$$ $$$( 1 \leq T \leq 10^3 )$$$, indicating the number of test cases.
For each test case, the first line contains three integers $$$n,R_2,R_3$$$ $$$(1\leq n\leq 10^5, 0\leq R_2,R_3\leq 10^6)$$$, representing the number of connection points, the sensor error radius, and the bird radius, respectively.
The next $$$ n $$$ lines each contain two integers $$$ x_i, y_i $$$ $$$( |x_i|, |y_i| \leq 10^6 )$$$, representing the $$$ i $$$-th connection point of the trajectory.
It is guaranteed that the sum of $$$ n $$$ over all test cases in a single test point does not exceed $$$ 10^5 $$$.
For each test case, output a single floating-point number representing the answer. Your answer is considered correct if the relative or absolute error compared to the standard answer is at most $$$ 10^{-9} $$$.
Let your answer be $$$ a $$$ and the standard answer be $$$ b $$$. If $$$ \frac{|a - b|}{\max\{b, 1\}} \leq 10^{-9} $$$, it is considered correct.
15 1 10 03 12 32 2-1 3
77.622211120429589
The convex hull of all points that the bird's center may pass through:
