题解：P6848 [CEOI2019] Scissors and Tape

· · 题解

upd on 2024.12.16：这几天写了一下终于过了，总共写了 9.5KB，比想象中要好写一些（？？），来补充一些实现上的细节。

作为 CEOI2019 的 Day2 T3，这题还是非常美味的。

题意：给出一个多边形 S，你可以将其任意裁剪拼接，使得它最终与多边形 T 等价。保证 S 与 T 面积相等。

首先考虑一些基本的情况：从长方形到另一个长方形。

我们称一个长方形是 优秀 的当且仅当它的长宽之比在 \dfrac12 到 2 之间。

如果当前的长方形不是优秀的，我们可以通过折半来使其长宽比尽量平均。

对于一个优秀的长方形，可以通过将其分成三部分来转化为另一个长方形。

具体的切割位置可以考虑观察左右图得到，例如左图中蓝色部分的下面那条边和黄色部分的上面那条边都等于右边长方形的长。

这样我们就实现了长方形之间的转化。接下来考虑三角形。

对于一个三角形，我们首先可以用一次 tape 操作将其一条边转到 x 轴上，接下来进行如下图的转化：

具体来说，先做出三角形的中位线（红色区域与另外两个区域的边界），再从顶部的点作垂，分出蓝色区域和绿色区域。这样将蓝色和绿色区域各旋转 180\degree 就可以变为长方形了。

而对于从一个长方形变为一个三角形，则同理：

  1. 首先将长方形的比例改成能对应上图的矩形大小（即长等于三角形的底，宽等于三角形的高的一半）；
  2. 从三角形上面顶点的位置向底下两个顶点连线，切出两边的两个小三角形；
  3. 将两个小三角形旋转 180\degree 度到上面，拼接起来。

所以，我们最终可以得到如下的一个操作步骤：

  1. 将 S 和 T 三角剖分；
  2. 对于 S 中的每个三角形 s，将其转化成一个矩形；
  3. 把所有的矩形全都转化成高相同的矩形，并拼接在一块成为大矩形 R_S；
  4. 根据 T 中每个三角形 t 的面积将 R_S 分成若干块，每一块对应一个三角形；
  5. 对于每一块 R_T 按照上面说的方法转化成对应的 T 中的三角形 t；
  6. 将所有的 t 按照原本的位置拼在一起，形成 T。

代码实现 非常 困难，由于 lz 暂时还没写完所以先不给了实际上也没那么困难，只要想清楚每一步都要干什么就还算清晰。

实现的时候有比较多的细节要注意：

  1. 题目要求所有的多边形输出的时候都要按照逆时针的顺序输出，这一点一定要注意！！！
  2. 因为多边形的点数不超过 10，三角剖分的时候可以考虑暴力枚举每一个点尝试将其去掉，需要保证其相邻的两个点连线不会与多边形的其它点连线相交，而且两点连线不能整个都在多边形外面，后者可以通过取连线的中点并用射线法判断是否在多边形内，这时注意一些边界问题（如射线和多边形的边的交点在顶点处）。
  3. 在把一个三角形转长方形的时候要注意不能随便选两个点就直接拖到 x 轴上，因为有可能另一个点会出现在 x 轴下方，后面要加各种特判，所以不如直接在前面选出一条另一个点不会出现在 x 轴下方的边，实际上直接选最长的那条边然后判断一下应该用哪一侧把剩下那个点转上来。
  4. 拼接出的大矩形的高不要太小，我最开始用的 H=1.14 结果精度炸飞了，最后改成 H=\sqrt{S} 就过了。

如果还有不清楚的地方，可以看 我的代码，看不懂的欢迎找我讨论。

实际上也有一些其它做法，比如可以发现两个正方形可以拼在一起然后转化为大正方形，于是可以把 S 的每个长方形都转化成正方形之后拼在一起变成大正方形，再倒过来拆出 T。