Problem E. Equidistant shell

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

The equidistant shell of a three-dimensional body is the set of points external to it, within a distance of no more than a given δ. Example of equidistant shell of cube with its cross section is presented on picture.

Given an arbitrary convex polyhedron and a value of δ. You program must calculate volume of the equidistant shell.

Input format

Input data contains original polyhedron presented in a following format.

First there is the integer V, followed by exactly 3 ⋅ V real numbers that are coordinates of the vertices.

Next, integer E, followed by exactly 2 ⋅ E numbers of the vertices, defining the edges pairwise.

Next is the integer F, followed by exactly F faces represented in the following format.

First integer number of edges N, followed by N indices of edges of this face in an arbitrary order.

Indices of the all elements start from zero.

The floating point value of δ is written at the end of the input data.

Output format

Output data must contain the volume with an accuracy of at least 5 digits after decimal point.

Constraints

All faces are non-degenerate and convex.

Vertex coordinates are in the range from  − 10 to 10.

Count of elements of each kind does not exceed 100.

0 ≤ δ ≤ 1

Sample tests

No. Standard input Standard output
1
8
-1.00000 -1.00000 -1.00000
 1.00000 -1.00000 -1.00000
-1.00000  1.00000 -1.00000
 1.00000  1.00000 -1.00000
-1.00000 -1.00000  1.00000
 1.00000 -1.00000  1.00000
-1.00000  1.00000  1.00000
 1.00000  1.00000  1.00000

12
1 0
2 0
4 0
3 1
5 1
3 2
6 2
7 3
5 4
6 4
7 5
7 6

6
4 3 5 1 0
4 4 8 2 0
4 6 9 2 1
4 7 4 10 3
4 7 11 6 5
4 10 11 9 8

0.25
7.24355

0.074s 0.010s 15