输入:N 个矩形。给出了矩形的坐标。
输出:检查它们是否形成正方形。
- 矩形之间可以有重叠。
我已经解决了矩形平行于X 和Y 轴的情况。
索恩:
由于正方形的面积是一个完美的正方形，所以 (所有矩形的面积之和 - 它们之间的重叠)应该是一个完美的正方形。
现在找到最小值。所有矩形的X坐标值和最大值。 Y 坐标值。 如果它们形成一个正方形，则 | min(x)-max(y) | 是正方形的长度。 现在只需计算考虑重叠的矩形面积之和。 如果它等于长度为 | 的正方形面积最小(x)-最大(y)|。宾果!!
复杂度:O(n*n)
一般情况如何解决？
最佳答案
假设所有矩形组成正方形，但矩形的边不平行于轴。
那么正方形有四个顶点:上、下、右、左。正方形的顶部顶点的 y 坐标 = 所有矩形的所有顶点的 y 坐标的最大值。以此类推其他三个顶点:底部(最小 y)、右侧(最大 x)和左侧(最小 x)。
要找到正方形的角度，只需两个顶点:底部和右侧。
设底部顶点坐标为 (someX, minY)，右侧顶点坐标为 (maxX, someY)。
那么角度就是atan((someY-minY)/(maxX-someX))。在 C/C++/Java/C# 中，您可以使用函数 atan2。
之后，将所有矩形旋转-angle，然后您可以将算法应用于与轴平行的矩形。
关于检查给定矩形是否形成正方形的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27826139/