Description

Two superheroes are fighting in the universe. To defeat his opponent Hero B, Hero A uses his ultimate move and fires an energy wave.

Hero B has some stamina. If the damage from Hero A’s energy wave is large enough, Hero B will be knocked down. Otherwise, Hero A will be caught off guard by Hero B after exhausting his energy, and Hero A will be knocked down instead. So Hero A urgently wants to know how much damage his energy wave can deal to Hero B.

To simplify the problem, Hero B can be described as an object made up of multiple convex polyhedra in space. These convex polyhedra may overlap. The overlapping part, as part of Hero B’s body, is counted only once.

The energy wave fired by Hero A can also be described as another convex polyhedron in space. This wave moves uniformly by a vector $\vec{v} = (v_x,v_y,v_z)$ per second. The energy wave can pass through any object, and deals damage while passing through it.

At time $t$, suppose the intersection volume of Hero A’s energy wave and Hero B’s body is $f(t) = V$. Then at that instant, the instantaneous damage rate caused by the energy wave is exactly $V$. The total damage over all time can be written as

Hero A wants to know the total damage his energy wave deals to Hero B’s body.

Input Format

The first line contains a positive integer $m_B$, indicating how many convex polyhedra make up Hero B’s body.

Then there are $m_B$ input blocks, each describing one component of Hero B’s body.

The first line of each block contains a positive integer $n$, indicating the number of vertices of this convex polyhedron.

The next $n$ lines each contain a triple. The $i$-th triple $(x_i,y_i,z_i)$ gives the coordinates of the $i$-th point.

Then one line contains a positive integer $n_A$, indicating the number of vertices of the convex polyhedron corresponding to Hero A’s energy wave.

The next $n_A$ lines each contain a triple. The $i$-th triple $(x_i,y_i,z_i)$ gives the coordinates of the $i$-th point.

Then one line contains a triple $(v_x,v_y,v_z)$, indicating the moving velocity of Hero A’s energy wave.

It is guaranteed that $1 \le m_B \le 4$, $4 \le n,n_A \le 8$. All input point coordinates are integers in $[-100,100]$. Each component of the velocity vector is a real number in $[-10,10]$. All convex polyhedra are non-degenerate (meaning the volume of the polyhedron is not $0$).

In the input, it may happen that four points are coplanar or three points are collinear.

It is guaranteed that at time $0$, the energy wave and Hero B do not intersect. Also, after $10^4$ seconds, the intersection volume is always $0$.

Output Format

Output one real number in one line, representing the value of the total damage.

Your answer will be considered correct if its absolute error or relative error is less than $10^{-6}$.

1
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
8
2 0 0
2 0 1
2 1 0
2 1 1
3 0 0
3 0 1
3 1 0
3 1 1
-1 0 0

1.0000000000

Hint

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5