# 963. Minimum Area Rectangle II 最小面积矩形 II

@TOC

## # 题目描述

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. 1 <= points.length <= 50
2. 0 <= points[i][0] <= 40000
3. 0 <= pointsiopen in new window <= 40000
4. All points are distinct.
5. Answers within 10^-5 of the actual value will be accepted as correct.

## # 解题方法

### # 线段长+线段中心+字典

1. 长方形的两条对角线长度相等；
2. 长方形的两条对角线互相平分（中点重合）；

python代码如下：

``````class Solution(object):
def minAreaFreeRect(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
N = len(points)
# (l^2, x#, y#) : [(0,1), (1,2)]
d = collections.defaultdict(list)
for i in range(N - 1):
pi = points[i]
for j in range(i + 1, N):
pj = points[j]
l = (pi[0] - pj[0]) ** 2 + (pi[1] - pj[1]) ** 2
x = (pi[0] + pj[0]) / 2.0
y = (pi[1] + pj[1]) / 2.0
d[(l, x, y)].append((i, j))
res = float("inf")
for l in d.values():
M = len(l)
for i in range(M - 1):
p0, p2 = points[l[i][0]], points[l[i][1]]
for j in range(i + 1, M):
p1, p3 = points[l[j][0]], points[l[j][1]]
d1 = math.sqrt((p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2)
d2 = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
area = d1 * d2
res = min(res, area)
return 0 if res == float('inf') else res
``````

## # 日期

2018 年 12 月 23 日 —— 周赛成绩新高