#P17734. [ICPC 2019 Xuzhou R] Polycut
[ICPC 2019 Xuzhou R] Polycut
Problem Description
You are given a convex polyhedron with vertices and edges. The polyhedron is somewhat ugly, thus you want to cut it into a different shape.
You've chosen planes in the 3-dimensional space. A plane will cut a polyhedron into two polyhedra. If the polyhedron lies completely on one side of the plane, we define one of the polyhedra is an empty set (which has zero volume). Thus, the planes will cut the polyhedron into polyhedra.
You want to know the volume of each polyhedron after cutting. However, there are too many vertices in the original polyhedron, so you need to write a program to calculate the answer.
Input Format
The first line contains three positive integers () --- the number of vertices and edges in the polyhedron, and the number of planes.
Each of the next lines contains three integers () --- the coordinate of the -th vertex. The vertices are numbered from to .
Each of the next lines contains two integers (), indicating that there is an edge connecting the -th and the -th vertex.
Each of the next lines contains four integers (), indicating a plane with equation .
Output Format
Output real numbers, each in a line, representing the volume of each polyhedron after cutting. The numbers must be sorted in non-decreasing order.
Your answer will be considered correct if the relative or absolute error does not exceed .
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