P2358 蚂蚁搬家 计算几何

Genius_Star · 2023-06-25 16:34:48 · 题解

题意理解：

• 给定一个边长为 1 的正方体，从上表面某一点出发，到达下表面某一点，求最短路径。

• 蚂蚁只能沿正方体表面爬行，即只能走正方体的表面，不能穿过正方体。

• 可以将上表面地面和下表面抽象成平面，且两个平面的坐标系的 X 轴和 Y 轴方向一致。

• 输入起点和终点的坐标。

• 输出最短距离，保留三位小数。

思路分析：

• 将正方体展开成一些小的区域，每个区域都是一个正方形，一共有 6 个面，每个面包含 9 个小正方形。

• 可以将蚂蚁从上表面的某一点 a 移动到下表面的某一点 b，等价于在正方体的某个面上沿着正方形的边界从 a 到 b，再绕过正方体到达目标面的 b 点。

• 蚂蚁从 a 点到 b 点的最短路径，可以分解成两步走：

  • 第一步：蚂蚁从 a 点走到某个面的边界上的一个点 c，这个点 c 可以是 a 点所在的面上的点，也可以是正方体的另一个面上的点。

  • 第二步：蚂蚁从 c 点到达目标面的 b 点，也就是在目标面的边界上找到一个点 d，使得 c 点和 d 点连线的长度最短。

• 对于第一步，可以将正方体展开，将正方体的每个面都展开成一个矩形，将 a 点和 b 点所在的面展开到同一个平面上，然后在平面上寻找一条最短路径，使得蚂蚁从 a 点到达正方体的边界。

• 对于第二步，可以先将正方体的一个面展开，并将起点 c 映射到展开面上的一个点 C，将终点 b 映射到展开面上的一个点 D，然后在展开面上找到一条最短路径，使得蚂蚁从 C 点到达 D 点，再将这个路径映射回正方体的表面。

• 最后将两个步骤的路径长度相加就是蚂蚁从 a 点到 b 点的最短路径。

  代码：

  额，写的太丑了，就不拿出来丢人现眼了~

不过你通过上述的推导应该能自己写出来了吧！