Dice Landing Probability

Consider a dice which is a homogeneous convex polyhedron. It has several faces, and every face is a convex polygon; moreover, no two faces lie on the same plane. When the dice is thrown, it lands without any secondary bounce (an ideal situation).

We assume that O is the center of mass of the dice. Center a unit sphere S (radius = 1) at O. The total surface area of S is (4\pi). For a given face (C), there exists a region (T) on S such that if the direction of gravity (projected to S) falls inside (T), then face (C) is the one that lands on the ground. Thus, the probability that face (C) lands is (\displaystyle \frac{\text{Area}(T)}{4\pi}).

To help calculate the area on the sphere, we recall the formula for the area of a spherical triangle on S. Suppose three great circles on S intersect pair‐wise at points A, B, and C (each pair of circles has a common intersection) and let (\alpha, \beta, \gamma) be the three corresponding dihedral angles. Then the area of the spherical triangle (ABC) is given by: [ \text{Area}(ABC)=\alpha+\beta+\gamma-\pi ]

For each face of the dice we assume that when it lands, the orthogonal projection of the center of mass falls strictly inside that face (i.e. no unstable or ambiguous cases occur).

In this problem, you are given the spherical polygon corresponding to the landing region (T) for each face. Each such polygon is represented by a list of vertices on the unit sphere given in spherical coordinates ((\theta, \phi)) (in radians). Here (\theta) is the polar angle (from the positive (z)-axis) and (\phi) is the azimuthal angle (in the (xy)-plane from the positive (x)-axis). For a spherical polygon with (m) vertices, its area is computed by first calculating the internal angles at each vertex (by projecting the adjacent vertices onto the tangent plane at that vertex) and then applying the formula for a spherical polygon: [ \text{Area}=\sum_{i=1}^{m}\theta_i-(m-2)\pi. ]

Finally, the landing probability of a face equals its spherical region area divided by (4\pi).

inputFormat

The input begins with an integer (f) ((f \geq 1)) indicating the number of faces (test cases). Then, for each face, the input is given as follows:

• A line containing an integer (m) (the number of vertices of the spherical polygon representing the landing region of that face).
• Then (m) lines follow, each containing two floating–point numbers (\theta) and (\phi) (in radians) which represent the spherical coordinates of a vertex on the unit sphere. The vertices are given in order (either clockwise or counter–clockwise) and the polygon is guaranteed to be convex.

Note that the calculated landing probability for each face is given by: [ P = \frac{\text{Area of the spherical polygon}}{4\pi} ] where the area of a spherical polygon with (m) vertices is: [ \text{Area} = \Bigl(\sum_{i=1}^{m}\theta_i\Bigr) - (m-2)\pi ] (Here, (\theta_i) denote the internal angles at the vertices computed via spherical geometry methods.)

For conversion from spherical to Cartesian coordinates, use: [ x = \sin\theta\cdot\cos\phi,\quad y = \sin\theta\cdot\sin\phi,\quad z = \cos\theta. ]

Your program should read the input, compute the landing probability for each face and output (f) lines, each containing the probability (a floating point number with 6 decimal places).

outputFormat

Output (f) lines. The (i)th line should contain a floating point number representing the landing probability of the (i)th face. The probability is computed as the area of its spherical polygon divided by (4\pi). Print the answer with 6 decimal places.

sample

3
3
1.5708 0
1.5708 2.0944
1.5708 4.18879
3
0.7854 0
0.7854 2.0944
0.7854 4.18879
4
1.0472 0
1.0472 1.5708
1.0472 3.1416
1.0472 4.71239

0.500000
0.076970
0.204900