33OJ
登录 注册

#P17734. [ICPC 2019 Xuzhou R] Polycut

[ICPC 2019 Xuzhou R] Polycut

Problem Description

You are given a convex polyhedron with NN vertices and MM edges. The polyhedron is somewhat ugly, thus you want to cut it into a different shape.

You've chosen KK 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 KK planes will cut the polyhedron into 2K2^K 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 N,M,KN, M, K (N≤M≤3×104,K≤3N\leq M\leq 3\times 10^4, K\leq 3) --- the number of vertices and edges in the polyhedron, and the number of planes.

Each of the next NN lines contains three integers 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) --- the coordinate of the ii-th vertex. The vertices are numbered from 00 to N−1N-1.

Each of the next MM lines contains two integers u,vu,v (0≤u,v<N0\leq u,v<N), indicating that there is an edge connecting the uu-th and the vv-th vertex.

Each of the next KK lines contains four integers a,b,c,da, b, c, d (−109≤a,b,c,d≤109-10^9\leq a,b,c,d\leq 10^9), indicating a plane with equation ax+by+cz=dax+by+cz=d.

Output Format

Output 2K2^K 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 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