#2549. [Ctsc2010杀菌计划]
[Ctsc2010杀菌计划]
Description
栋栋有一个凸多面体形状的漂亮盒子,这个盒子的每个面都由形状为凸多边 形的透明玻璃薄壁组成。 每隔一段时间,栋栋就要使用一个激光发射器给他的盒子杀菌。激光发射器 能发射出一束激光,当激光照射到盒子的玻璃薄壁时,会把薄壁内外两面的细菌 杀死,同时有大量光线透射过玻璃,少量光线被玻璃反射。透射过玻璃的光线沿 原方向前进,反射的光线遵循光线的镜面反射定理,即在反射时反射光线、入射 光线和镜面的法线在同一平面内,反射光线与入射光线分居法线两侧,反射角(反 射光线与法线的夹角)等于入射角(入射光线与法线的夹角)。 我们认为激光被玻璃反射 k次后的能量不足以杀死细菌(即使有多个这样的 光线同时照射在玻璃薄壁上也不能杀死细菌),而 k 次反射前激光照射到的细菌 都会被杀死。 激光发射器的发射口是三角形的,当发射激光时,整个发射口都会发出激光。 给定盒子和激光发射器的位置,栋栋想知道,盒子的玻璃薄壁上有多大面积 的细菌被杀死了。由于盒子的内外两面的细菌必然是同时被杀死或者同时不被杀 死,所以只要算出外面被杀死的细菌面积即可。 注意,激光或经过反射的激光可能与某些表面平行,但本题的数据保证激光 或经过反射的激光不会照射到与之平行的表面。
Format
Input
每个输入数据满足下面的输入格式,每两个数之间用一个空格隔开:
输入的第一行包含三个整数 n, m, k,分别表示盒子的顶点数、盒子的面数和光线的反射次数。接下来 n行,第 i 行包含三个实数xi, yi, zi,表示盒子第 i 个顶点的坐标。接下来 m行,每行描述盒子的一个表面,每行第一个数 tj,表示该表面的多边形的顶点个数,接下来 tj个整数,表示这 tj个顶点对应的盒子顶点的编号,这些编号按顶点在面上的顺时针或逆时针顺序给出。接下来三行,每行 3个整数x, y, z,分别表示激光发射器发射口的坐标。接下来 1行,包含 3个整数Δx, Δy, Δz,表示出射光线的方向是沿着向量(Δx,Δy, Δz)的方向。
Output
每个输出文件包含一个实数,四舍五入保留两位小数, 表示被杀死的细菌的面积。当一个表面被多次照射到时,这个表面的面积只计算 一次。
Samples
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