💡题解与思路

🔍问题简化理解：

给定两个简单多边形 $P$ 和 $Q$，分别位于 $z=0$ 和 $z=10$ 的两个平面上；

每个多边形边可视作一个三角形的一边，另外两个点分别来自另一个多边形的一个顶点；

目标是选择一种三角形匹配策略，使得所有三角形覆盖了两多边形边，总侧面积之和最小。

🧮建模方式：

我们可以将这个问题视作 多边形边界之间的“带权匹配”问题。其核心思想是动态规划 + 几何计算：

状态定义： 设 dp[i][j] 表示第一个多边形前 $i$ 条边和第二个多边形前 $j$ 条边所构成的最小侧表面积。

状态转移： 通过比较将：

第 $i$ 条边和第 $j$ 个点组成三角形；

或者第 $j$ 条边和第 $i$ 个点组成三角形； 选择面积最小的路径转移。

面积计算（使用叉乘 or 海伦公式）： 三角形面积公式（考虑三维）：

𝑆

1 2 ⋅ ∣ 𝐴 𝐵 × 𝐴 𝐶 ∣ S= 2 1 ​ ⋅∣AB×AC∣ 其中 $A, B, C$ 是三维空间三角形的三个点。

✅解法总结步骤：

将两多边形点坐标转为三维坐标，分别赋 $z = 0$ 和 $z = 10$；

构建两多边形边数的动态规划表；

对所有可能的三角形组合使用几何公式计算面积；

使用动态规划求解最小面积；

四舍五入输出总面积。

代码实现