Safe Places |
There are n kinds (i.e. type-1, type-2, ..., type-n) of m satellites in the space. For each 1in, all the type-i satellites are working together to protect their minimal enclosing convex polyhedron (though its volume might be zero). If a point is protected by at least k kinds of satellites, we say this point is safe.
Find the volume of all safe places (it might be zero).
Note: The coordinates of satellites in the judge input (not sample input) are randomly generated.
2 2 1 16 1 0 0 0 1 0 0 2 1 0 2 0 1 0 2 2 1 2 0 0 1 2 0 2 1 2 2 0 1 2 2 2 2 1 1 1 2 1 1 3 2 1 3 1 2 1 3 3 2 3 1 1 2 3 1 3 2 3 3 1 2 3 3 3 1 1 4 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0
15.00000 0.16667