33OJ
登录 注册

#P17734. [ICPC 2019 Xuzhou R] Polycut

[ICPC 2019 Xuzhou R] Polycut

题目描述

给定一个具有 NN 个顶点和 MM 条棱的凸多面体。这个多面体有些丑陋,因此你想将其切割成不同的形状。

你在三维空间中选择了 KK 个平面。每个平面会将一个多面体切割成两个多面体。如果原多面体完全位于平面的某一侧,我们定义其中一个多面体为空集(其体积为零)。因此,这 KK 个平面会将多面体切割成 2K2^K 个多面体。

你想知道切割后每个多面体的体积。但由于原多面体的顶点过多,你需要编写一个程序来计算答案。

输入格式

第一行包含三个正整数 N,M,KN, M, K (N≤M≤3×104N\leq M\leq 3\times 10^4, K≤3K\leq 3) —— 分别表示多面体的顶点数、棱数以及平面个数。

接下来的 NN 行,每行包含三个整数 xi,yi,zix_i, y_i, z_i (−104≤xi,yi,zi≤104-10^4\leq x_i,y_i,z_i\leq 10^4) —— 第 ii 个顶点的坐标。顶点从 00 到 N−1N-1 编号。

接下来的 MM 行,每行包含两个整数 u,vu,v (0≤u,v<N0\leq u,v<N),表示连接第 uu 个和第 vv 个顶点的一条棱。

接下来的 KK 行,每行包含四个整数 a,b,c,da, b, c, d (−109≤a,b,c,d≤109-10^9\leq a,b,c,d\leq 10^9),表示一个平面,其方程为 ax+by+cz=dax+by+cz=d。

输出格式

输出 2K2^K 个实数,每行一个,表示切割后每个多面体的体积。这些数字必须按非递减顺序排序。

若你的答案的相对误差或绝对误差不超过 10−610^{-6},则被视为正确。

8 12 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 1
1 3
3 2
2 0
4 5
5 7
7 6
6 4
0 4
1 5
2 6
3 7
3 0 0 1
0.333333333
0.666666667
4 6 1
0 0 0
0 0 3
0 2 0
1 0 0
0 1
0 2
0 3
1 2
1 3
2 3
1 1 1 0
0.000000000
1.000000000

提示

翻译由 DeepSeek V4 Pro 完成