{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given a convex polyhedron with $N$ vertices and $M$ edges. The polyhedron is somewhat ugly, thus you want to cut it into a different shape.\u003c/p\u003e\n\u003cp\u003eYou\u0027ve chosen $K$ 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 $K$ planes will cut the polyhedron into $2^K$ polyhedra.\u003c/p\u003e\n\u003cp\u003eYou 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.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line contains three positive integers $N, M, K$ ($N\\leq M\\leq 3\\times 10^4, K\\leq 3$) --- the number of vertices and edges in the polyhedron, and the number of planes.\u003c/p\u003e\n\u003cp\u003eEach of the next $N$ lines contains three integers $x_i, y_i, z_i$ ($-10^4\\leq x_i,y_i,z_i\\leq 10^4$) --- the coordinate of the $i$-th vertex. The vertices are numbered from $0$ to $N-1$.\u003c/p\u003e\n\u003cp\u003eEach of the next $M$ lines contains two integers $u,v$ ($0\\leq u,v\u0026lt;N$), indicating that there is an edge connecting the $u$-th and the $v$-th vertex.\u003c/p\u003e\n\u003cp\u003eEach of the next $K$ lines contains four integers $a, b, c, d$ ($-10^9\\leq a,b,c,d\\leq 10^9$), indicating a plane with equation $ax+by+cz\u003dd$.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eOutput $2^K$ real numbers, each in a line, representing the volume of each polyhedron after cutting. \u003cstrong\u003eThe numbers must be sorted in non-decreasing order.\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eYour answer will be considered correct if the relative or absolute error does not exceed $10^{-6}$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 12 1\n0 0 0\n0 0 1\n0 1 0\n0 1 1\n1 0 0\n1 0 1\n1 1 0\n1 1 1\n0 1\n1 3\n3 2\n2 0\n4 5\n5 7\n7 6\n6 4\n0 4\n1 5\n2 6\n3 7\n3 0 0 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.333333333\n0.666666667\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 6 1\n0 0 0\n0 0 3\n0 2 0\n1 0 0\n0 1\n0 2\n0 3\n1 2\n1 3\n2 3\n1 1 1 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.000000000\n1.000000000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}