Laser Reflection Sterilization on a Convex Polyhedron

Dongdong owns a beautiful box in the shape of a convex polyhedron. Every face of the box is made of a thin wall of transparent glass in the shape of a convex polygon. Periodically, Dongdong sterilizes the bacteria on the glass surfaces using a laser emitter.

The emitter has a triangular aperture which emits a laser beam from every point on the triangle. When the laser beam hits a glass face, it kills the bacteria on both its inside and outside surfaces. In addition, most of the light transmits through the glass while a small portion is reflected, following the law of specular reflection. That is, if the incident beam, the reflected beam, and the face normal all lie in the same plane and the angle between the incident beam and the normal equals the angle between the reflected beam and the normal.

We assume that if the laser is reflected k times, its energy becomes insufficient to kill bacteria (even if several such beams hit the same face simultaneously, they won’t sterilize). All bacteria hit by the laser within fewer than k reflections are killed.

Given the positions of the box and the laser emitter, Dongdong wants to know the total area of the box's glass that gets sterilized (note that since the bacteria on the two sides of a face are killed simultaneously, it is sufficient to count the area on one side).

Note: Although the laser or its reflections may become parallel to some faces, the input data guarantees that a laser beam (or its reflection) will never hit a face parallel to its direction.

Mathematical formulation:

Let E denote the centroid of the triangular emitter. For each face with area A, center C, and outward unit normal n, define the hit condition as follows:

• Direct hit (0 reflections): if (E - C) \cdot n > 0.
• One reflection: suppose face D is directly hit and has unit normal n_D. Let d = (E - P_D) \cdot n_D for some point P_D on D, and let the mirror image be E' = E - 2d\,n_D. Then an adjacent face F is hit with one reflection if (E' - C_F) \cdot n_F > 0 (where C_F and n_F are the center and outward normal of F).
• If at least two reflections are allowed (k >= 2), the sterilization covers the entire outer surface of the box.

The input guarantees that all necessary geometric computations (such as determining adjacent faces and computing face areas) can be performed without ambiguities. In this problem, you are to compute the total sterilized area on the external side of the box.

Input (in brief): The first line contains two integers n and k, where n is the number of faces of the polyhedron and k is the maximum number of reflections for which the laser still kills bacteria. This is followed by the description of each face. For each face, the first number is an integer m (the number of vertices), then m lines follow, each with three real numbers representing the coordinates of the vertices in order. After the faces, three lines follow giving the coordinates of the vertices of the triangular emitter.

Output: Output a real number – the total area of the box’s glass (one side) that has been sterilized. Print your answer with at least six digits after the decimal point.

Hint (in LaTeX):

If $E$ is the centroid of the emitter and $C_F$ is the center of a face $F$ with normal $n_F$, then the face is directly hit if $$ (E - C_F) \cdot n_F > 0. $$ For a face $D$ that is directly hit, let $$ E' = E - 2\,((E-P_D)\cdot n_D)n_D, $$ where $P_D$ is any point on $D$. Then for an adjacent face $F$, the one-reflection condition is $$ (E' - C_F) \cdot n_F > 0. $$

inputFormat

The first line contains two numbers: an integer n (the number of faces) and an integer k (the maximum number of reflections for which the laser is effective). Then, for each face, the input is structured as follows:

m
x1 y1 z1
x2 y2 z2
... 
xm ym zm

After the faces, there are 3 lines, each containing 3 real numbers, representing the coordinates of the vertices of the triangular emitter.

Sample (a cube example):

6 0
4
0 0 0
0 1 0
1 1 0
1 0 0
4
0 0 1
1 0 1
1 1 1
0 1 1
4
0 0 0
0 0 1
0 1 1
0 1 0
4
1 0 0
1 1 0
1 1 1
1 0 1
4
0 0 0
1 0 0
1 0 1
0 0 1
4
0 1 0
0 1 1
1 1 1
1 1 0
-0.2 0.2 -1
0.2 0.2 -1
0 0.6 -1

outputFormat

Output a single real number representing the total sterilized area on the external side of the box. The answer should be printed with at least six digits after the decimal point.

sample

6 0
4
0 0 0
0 1 0
1 1 0
1 0 0
4
0 0 1
1 0 1
1 1 1
0 1 1
4
0 0 0
0 0 1
0 1 1
0 1 0
4
1 0 0
1 1 0
1 1 1
1 0 1
4
0 0 0
1 0 0
1 0 1
0 0 1
4
0 1 0
0 1 1
1 1 1
1 1 0
-0.2 0.2 -1
0.2 0.2 -1
0 0.6 -1

1.000000