P4508 [CTSC2011] 杀菌计划

输入数据下发链接: https://pan.baidu.com/s/1ltIqAf8bdtnAFrFTnVtgHA

栋栋有一个凸多面体形状的漂亮盒子，这个盒子的每个面都由形状为凸多边形的透明玻璃薄壁组成。 每隔一段时间，栋栋就要使用一个激光发射器给他的盒子杀菌。激光发射器能发射出一束激光，当激光照射到盒子的玻璃薄壁时，会把薄壁内外两面的细菌杀死，同时有大量光线透射过玻璃，少量光线被玻璃反射。透射过玻璃的光线沿原方向前进，反射的光线遵循光线的镜面反射定理，即在反射时反射光线、入射光线和镜面的法线在同一平面内，反射光线与入射光线分居法线两侧，反射角（反射光线与法线的夹角）等于入射角（入射光线与法线的夹角）。 我们认为激光被玻璃反射k 次后的能量不足以杀死细菌（即使有多个这样的光线同时照射在玻璃薄壁上也不能杀死细菌），而k 次反射前激光照射到的细菌都会被杀死。 激光发射器的发射口是三角形的，当发射激光时，整个发射口都会发出激光。 给定盒子和激光发射器的位置，栋栋想知道，盒子的玻璃薄壁上有多大面积 的细菌被杀死了。由于盒子的内外两面的细菌必然是同时被杀死或者同时不被杀死，所以只要算出外面被杀死的细菌面积即可。 注意，激光或经过反射的激光可能与某些表面平行，但本题的数据保证激光或经过反射的激光不会照射到与之平行的表面。

本题是一道提交答案型试题，所有输入数据box1.in ~ box10.in 已放在了试题的目录下。每个输入数据满足下面的输入格式，每两个数之间用一个空格隔开： 输入的第一行包含三个整数$n, m, k$，分别表示盒子的顶点数、盒子的面数和光线的反射次数。 接下来$n$ 行，第$i$ 行包含三个实数$x_i, y_i, z_i$，表示盒子第$i$ 个顶点的坐标。 接下来$m$ 行，每行描述盒子的一个表面，每行第一个数$t_j$，表示该表面的多边形的顶点个数，接下来$t_j$ 个整数，表示这$t_j$ 个顶点对应的盒子顶点的编号，这些编号按顶点在面上的顺时针或逆时针顺序给出。 接下来三行，每行$3$ 个整数$x, y, z$，分别表示激光发射器发射口的坐标。 接下来$1$ 行，包含3 个整数$Δx, Δy, Δz$，表示出射光线的方向是沿着向量$(Δx, Δy, Δz)$的方向。

针对给定的10 个输入文件box1.in ~ box10.in，你需要分别提交你的输出文 件 box1.out ~ box10.out。每个输出文件包含一个实数，四舍五入保留两位小数，表示被杀死的细菌的面积。当一个表面被多次照射到时，这个表面的面积只计算一次。

样例数据如下图所示，盒子是一个正方体的形状，激光从右边照射过来，照 射到右侧面上，并透射过右侧面照射到左侧面上，将左右两侧面上的两个三角形区域的细菌杀死。在照射到左右侧面后激光都会发生反射，但由k=1，反射光线已不能将细菌杀死，所以不用考虑。