algorithm - 我该如何解决这个算法问题。最佳时间和空间复杂度是多少？

Question

你的 table 上有 𝑁 长方形纸，你想用别针将它们固定。给定职位，纸张的大小和方向，设计一个算法来确定它们是否可以固定只有一根针或没有。请注意，您不能移动或旋转纸张。

编辑:

我想到先把每张长方形纸分解成小三角形(利用三角分解法)，然后找出所有长方形纸共有的小网格区域。然后固定公共(public)区域

Answer 1

这与图形编程中用于“裁剪”的算法相同。从第一张纸开始，用下一张矩形纸夹住剩余的重叠多边形。所有生成的多边形都是凸的，因此可以使用 2D 凸多边形裁剪算法。 This one将执行交集的步骤列为:

1. Create an empty polygon as P
2. Add all corners of Polygon1 that is inside Polygon2 to P
3. Add all corners of Polygon2 that is inside Polygon1 to P
4. Add all intersection points to P

如果在任何一点上都没有交点，那么就没有放置图钉的地方。

参见 this SO Q&A了解更多想法。