Description

Dongdong has a beautiful box shaped like a convex polyhedron. Each face of the box is a thin, transparent glass panel in the shape of a convex polygon.

From time to time, Dongdong uses a laser emitter to sterilize his box. The emitter emits a laser beam. When the beam hits a glass panel, it kills the bacteria on both the inner and outer sides of that panel. A large portion of the light transmits through the glass, and a small portion is reflected. The transmitted light continues in the same direction. The reflected light obeys the law of specular reflection: at the point of reflection, the reflected ray, the incident ray, and the surface normal lie in the same plane; the reflected ray and the incident ray lie on opposite sides of the normal; and the angle of reflection (between the reflected ray and the normal) equals the angle of incidence (between the incident ray and the normal).

We assume that after being reflected $k$ times, the laser does not have enough energy to kill bacteria (even if multiple such rays hit a glass panel simultaneously, they still cannot kill bacteria). Before $k$ reflections, all bacteria illuminated by the laser are killed.

The emitter’s aperture is triangular, and when the laser is fired, the entire aperture emits light.

Given the box and the position of the laser emitter, Dongdong wants to know the total area of bacteria killed on the box’s glass panels. Since the bacteria on the inner and outer sides of a panel are either both killed or both not killed, it suffices to compute the area killed on the outside.

Note: A laser ray or a reflected ray may be parallel to some surfaces, but the testdata guarantees that no ray will illuminate any surface that is parallel to it.

Input Format

This is an answer-only problem. All input files box1.in ~ box10.in are provided in the problem directory. Each input file follows the format below, with a single space between any two numbers.

• The first line contains three integers $n, m, k$, denoting the number of vertices of the box, the number of faces, and the reflection limit, respectively.
• The next $n$ lines: line $i$ contains three real numbers $x_i, y_i, z_i$, which are the coordinates of vertex $i$ of the box.
• The next $m$ lines: each line describes one face of the box. The first number is $t_j$, the number of vertices of this polygonal face, followed by $t_j$ integers giving the indices of the corresponding box vertices in clockwise or counterclockwise order along the face.
• The next three lines: each contains $3$ integers $x, y, z$, giving the coordinates of the laser emitter’s triangular aperture (these are its three vertices).
• The next one line contains $3$ integers $\Delta x, \Delta y, \Delta z$, indicating that the emitted rays travel in the direction of the vector $(\Delta x, \Delta y, \Delta z)$.

Output Format

For the given 10 input files box1.in ~ box10.in, you must submit 10 corresponding output files box1.out ~ box10.out. Each output file contains a single real number, rounded to two decimal places, representing the total area of bacteria killed. If a face is illuminated multiple times, its area is counted only once.

8 6 1
0.0 0.0 0.0
0.0 0.0 1.0
0.0 1.0 1.0
0.0 1.0 0.0
1.0 0.0 0.0
1.0 0.0 1.0
1.0 1.0 1.0
1.0 1.0 0.0
4 2 3 7 6
4 5 6 7 8
4 1 2 3 4
4 1 2 6 5
4 4 3 7 8
4 1 4 8 5
2.0 0.33 0.25
2.0 0.67 0.25
2.0 0.33 0.75
-1.0 0.0 0.0

0.17

Hint

As shown in the sample figure, the box is a cube. The laser comes from the right, hits the right face, and, after transmitting through the right face, hits the left face, killing two triangular regions on the left and right faces. The rays also reflect at both faces, but since $k = 1$, the reflected rays can no longer kill bacteria, so they can be ignored.

Translated by ChatGPT 5