UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2602. [Ctsc2010杀菌计划]

统计 下载数据

Description

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

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


每个输出文件包含一个实数,四舍五入保留两位小数,
表示被杀死的细菌的面积。当一个表面被多次照射到时,这个表面的面积只计算
一次。

Sample Input

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

Sample Output


0.17

Hint

Source