1 条题解

  • 0
    @ 2025-10-19 16:02:10

    题意

    给一个地面(平面)、一个点光源、一个凸多面体,求凸多面体在地面上的投影面积。


    核心思路

    1. 投影方法
      从点光源向凸多面体的每个顶点引射线,与地面相交,这些交点的凸包就是阴影区域。

    2. 求射线与地面的交点
      设光源为 PP,多面体顶点为 AA,射线 P+t(AP)P + t(A - P) 与地面相交。
      地面由三点 Q1,Q2,Q3Q_1, Q_2, Q_3 确定,平面方程可求出:
      n=(Q2Q1)×(Q3Q1)\vec{n} = (Q_2 - Q_1) \times (Q_3 - Q_1),平面方程 n(XQ1)=0\vec{n} \cdot (X - Q_1) = 0
      将射线代入: [ \vec{n} \cdot (P + t(A - P) - Q_1) = 0 ] 解得 [ t = \frac{\vec{n} \cdot (Q_1 - P)}{\vec{n} \cdot (A - P)} ] 交点 X=P+t(AP)X = P + t(A - P)

    3. 特殊情况
      如果 n(AP)=0\vec{n} \cdot (A - P) = 0,说明射线与地面平行(无交点或无穷远),但题目保证面积有限且不为零,所以可忽略无穷情况。

    4. 求阴影面积
      将所有交点求二维凸包(在地面坐标系下),然后计算凸包面积。


    步骤

    1. 读入地面三点 Q1,Q2,Q3Q_1, Q_2, Q_3,计算法向量 n\vec{n}
    2. 读入光源 PP
    3. 读入 nn 个顶点 AiA_i
    4. 对每个 AiA_i,计算 $t = \frac{\vec{n} \cdot (Q_1 - P)}{\vec{n} \cdot (A_i - P)}$,得到交点 Xi=P+t(AiP)X_i = P + t(A_i - P)
    5. XiX_i 投影到地面坐标系(可选步骤,也可直接用三维凸包在平面上的投影计算面积)。
    6. 对投影点集求二维凸包,计算凸包面积。
    7. 输出面积,保留两位小数。

    注意

    • 由于是凸多面体,其投影也是凸多边形。
    • 地面由任意三点确定,需要建立局部坐标系来求二维凸包。
    • 1

    「2017 山东一轮集训 Day2 / SDWC2018 Day1」Shadow

    信息

    ID
    3363
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者