题目描述

有两个超级英雄在宇宙中战斗。英雄 A 为了击败对手英雄 B，使出了他的绝招，发出了一记能量光波。

英雄 B 有一些体力值，如果英雄 A 的能量光波对英雄 B 的伤害足够大，英雄 B 就会被击倒。否则英雄 A 就会因为耗尽能量而被英雄 B 抓住破绽，从而反而被英雄 B 击倒。所以英雄 A 迫切想知道自己的能量光波到底能够对英雄 B 造成多少伤害。

为了简化问题，英雄 B 可以被描述为空间中的多个凸多面体拼成的物体。这些凸多面体可能有重合的部分，重合部分作为英雄 B 的身体只会被计算一次。

英雄 A 发出的能量光波也可以被描述为空间中的另外一个凸多面体，这个光波在空间中每秒均匀移动一个向量 $\vec{v} = (v_x,v_y,v_z)$。能量光波可以穿过任何物体，并且在穿越的过程中对对方造成伤害。

在时刻 $t$, 假设英雄 A 的能量光波和英雄 B 的身体的交的体积为 $f(t) = V$，那么在这一瞬间，能量光波造成的瞬时伤害速率就恰好是 $V$。而所有时刻的总计伤害就可以被表示为

英雄 A 想要知道自己的能量光波对英雄 B 的身体造成了多大的总计伤害。

输入格式

第 $1$ 行一个正整数 $m_B$，表示英雄 B 的身体有多少个凸多面体组成。

接下来有 $m_B$ 个输入块，每块表示英雄 B 的身体的一个组成部分。

每个输入块开头第一行为一个正整数 $n$，表示这个凸多面体的顶点的个数，

接下来 $n$ 行每行一个三元组，其中第 $i$ 个 $(x_i,y_i,z_i)$ 表示第 $i$ 个点的坐标。

接下来一行一个正整数 $n_A$，表示英雄 A 的能量光波的对应凸多面体的顶点数，

接下来 $n_A$ 行每行一个三元组，其中第 $i$ 个 $(x_i,y_i,z_i)$ 表示第 $i$ 个点的坐标。

再接下来一行一个三元组 $(v_x,v_y,v_z)$，表示英雄 A 的能量光波的移动速度。

我们保证 $1 \le m_B \le 4,4\le n,n_A\le 8$ ，所有输入的点的坐标都是 $[-100,100]$ 内的整数。并且所有速度向量的分量都是 $[-10,10]$ 内的实数。所有凸多面体都是不退化的 （意思是这个凸多面体的体积非 $0$）。

输入中可能会出现四点共面或者三点共线的情况。

我们保证在第 $0$ 秒能量光波和英雄 B 是不相交的。并且在第 $10^4$ 秒之后交集的体积一直是 $0$。

输出格式

一行输出一个实数，表示总计伤害的值。

输出与标准答案的绝对误差或相对误差小于 $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

提示

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。