P17734 [ICPC 2019 Xuzhou R] Polycut

给定一个具有 $N$ 个顶点和 $M$ 条棱的凸多面体。这个多面体有些丑陋，因此你想将其切割成不同的形状。 你在三维空间中选择了 $K$ 个平面。每个平面会将一个多面体切割成两个多面体。如果原多面体完全位于平面的某一侧，我们定义其中一个多面体为空集（其体积为零）。因此，这 $K$ 个平面会将多面体切割成 $2^K$ 个多面体。 你想知道切割后每个多面体的体积。但由于原多面体的顶点过多，你需要编写一个程序来计算答案。

第一行包含三个正整数 $N, M, K$ ($N\leq M\leq 3\times 10^4$, $K\leq 3$) —— 分别表示多面体的顶点数、棱数以及平面个数。 接下来的 $N$ 行，每行包含三个整数 $x_i, y_i, z_i$ ($-10^4\leq x_i,y_i,z_i\leq 10^4$) —— 第 $i$ 个顶点的坐标。顶点从 $0$ 到 $N-1$ 编号。 接下来的 $M$ 行，每行包含两个整数 $u,v$ ($0\leq u,v

输出 $2^K$ 个实数，每行一个，表示切割后每个多面体的体积。**这些数字必须按非递减顺序排序。** 若你的答案的相对误差或绝对误差不超过 $10^{-6}$，则被视为正确。

翻译由 DeepSeek V4 Pro 完成