题目
题目
解题思路
- 找出所有的矩形
- 逐一计算面积，找出面积最小的矩形
对于步骤1，判断是否为矩形的条件是：其对角线相交的中心点到四个角的距离相等。如下图所示：
矩形判断
这里有个小技巧，为了对 list 中的点进行向量计算，我们使用 complex() 函数将这些点变为复数形式。complex用法示例如下：
>>> complex(1, 2)
>>> (1 + 2j)
忘了向量运算的，可以稍微复习一下：
向量加法：A（x1, y1) + B (x2, y2) = （x1 + x2, y1 + y2）
向量减法：A（x1, y1) - B (x2, y2) = （x1 - x2, y1 - y2）
参考代码（beats 95%）：
'''
@auther: Jedi.L
@Date: Tue, Apr 30, 2019 3:40
@Email: xiangyangan@gmail.com
@Blog: www.tundrazone.com
'''
import itertools
import collections
class Solution(object):
def minAreaFreeRect(self, points):
points = [complex(*z) for z in points]
seen = collections.defaultdict(list)
for P, Q in itertools.combinations(points, 2):
center = (P + Q) / 2 # get the center point
radius = abs(center - P) # caculate the distance
# Only record P here, because Q = 2 * center - P
seen[center, radius].append(P)
res = float("inf")
for (center, radius), candidates in seen.items():
for P, Q in itertools.combinations(candidates, 2):
# caculate area
res = min(res, abs(P - Q) * abs(P - (2 * center - Q)))
return res if res < float("inf") else 0
