963. Minimum Area Rectangle II

963. Minimum Area Rectangle II

难度: Medium

刷题内容

原题连接

内容描述

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn't any rectangle, return 0.



Example 1:



Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.
Example 2:



Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.
Example 3:



Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.
Example 4:



Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.


Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

解题方案

思路 1
- 时间复杂度: O(N^3)- 空间复杂度: O(N)

现将points全部存到lookup里面

三轮循环,每轮循环分别取一个点,p1,p2,p3,然后看看直线p1-p2和直线p1-p3是否是互相垂直的,因为我们打算让p2和p3作为对角线
(其实一共有三种组合方式,p2-p3,p1-p2,p1-p3都可以作为对角线)

  1. 如果互相垂直,那么算出最后一个点的坐标看看是否在lookup里面
    • 如果在,算出面积,更新
    • 如果不在,continue
  2. 如果不相互垂直,continue

```python
class Solution(object):
def minAreaFreeRect(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
lookup = {}
for p in points:
x, y = p
lookup[(x,y)] = 1

top Created with Sketch.