[LeetCode]Minimum Area Rectangle II

题目链接

这道题和I不同的地方在于并不是要求矩形是平行于x或者y轴的，这样就加大了难度，因为枚举对角线无法唯一确定矩形了。这个时候就需要改变方法，枚举所有可能的三个点，p0, p1和p2，我们要验证以下性质：

• 向量(p0, p1)垂直于(p0, p2)
• 确定能够形成矩形的第四个点p3，看其是否在点集当中
• 确定p3的方法很直观
• p3.x = p1.x - p0.x + p2.x - p0.x
• p3.y = p1.y - p0.y + p2.y - p0.y

同理我们要实现Point class然后用hashset存所有的点，这样的话时间复杂度为O(n^2)。代码如下：

另外一种方法是，对于任意两个point，我们计算对应的中点center和半径r，如果存在另外一对point的pair，有相同的中点和半径，那么这两对point pair就可以组成一个矩形。所以我们用一个Point到hashmap<radius, list<point>>，来存一个point pair的信息：

• 对于center来说，我们可以存2 * center.x和2* center.y来避免出现小数的情况
• radius的话，我们存r^2即可，这样也一定是整数，否则double当hashmap的key很不好
• point我们存一个即可，因为另外一个可以根据center算出来

建好之后我们遍历整个map即可，因为任何一个<center, radius>对应的point list，里面两两都可以形成矩形，我们枚举所有，然后更新最小值即可。时间复杂度不太好分析，但是根据LeetCode Solution的解答是可以达到O(N * log N)，具体可以参考那篇解答。代码如下：