题解 P4508 【[CTSC2011]杀菌计划】
算法1 (k=1时)
对于每个面 f
计算光线投射到 f 平面上时与 f 的交的面积
对所有 f 求出的面积求和
求光线在平面 f 上投射后的图形
将光源平面的每个顶点投影
设 p0, p1, p2是 f 上不共线的三个点，w是光源上的点，d是光线的方向，则
投影点 – p0 = x (p1 – p0) + y (p2 – p0) = w + z d
由上式解三元一次方程组即可求出投影点
x, y 可作为点 w 在平面 f 上的二维坐标，由于p1 – p0和p2 – p0可能不垂直，在使用此坐标计算面积时需要考虑他们的夹角 求两个凸多边形的交的面积
利用投射的方法转换成二维，在二维空间上计算交的面积
算法2 (k>1 时 ）
对于每个面 f
计算光源和 f 的交 T，在 f 上记录T
将T作为新的光源，根据入射光线方向和 f 的法向计算出射方向，即新光源的方向
若还能够反射，则递归处理
递归完成后，对于每个面 f
计算所有记录在 f 上的交T的并的面积
对所有 f 求出的面积求和
计算反射光线
令入射向量为 d，法线向量为 n, 则出射向量为d – 2 (d · n) / (n · n) n; (其中 · 表示点积)
n可使用平面上两个不共线向量的叉积得到，上式与n的正反性无关
求凸多边形并的面积
和交的面积的计算类似，投射到二维平面计算