#P17734. [ICPC 2019 Xuzhou R] Polycut
[ICPC 2019 Xuzhou R] Polycut
题目描述
给定一个具有 个顶点和 条棱的凸多面体。这个多面体有些丑陋,因此你想将其切割成不同的形状。
你在三维空间中选择了 个平面。每个平面会将一个多面体切割成两个多面体。如果原多面体完全位于平面的某一侧,我们定义其中一个多面体为空集(其体积为零)。因此,这 个平面会将多面体切割成 个多面体。
你想知道切割后每个多面体的体积。但由于原多面体的顶点过多,你需要编写一个程序来计算答案。
输入格式
第一行包含三个正整数 (, ) —— 分别表示多面体的顶点数、棱数以及平面个数。
接下来的 行,每行包含三个整数 () —— 第 个顶点的坐标。顶点从 到 编号。
接下来的 行,每行包含两个整数 (),表示连接第 个和第 个顶点的一条棱。
接下来的 行,每行包含四个整数 (),表示一个平面,其方程为 。
输出格式
输出 个实数,每行一个,表示切割后每个多面体的体积。这些数字必须按非递减顺序排序。
若你的答案的相对误差或绝对误差不超过 ,则被视为正确。
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 完成