Table of Content
题目
解题思路
- 找出所有的矩形
- 逐一计算面积，找出面积最小的矩形
对于步骤1，判断是否为矩形的条件是：其对角线相交的中心点到四个角的距离相等。如下图所示：
这里有个小技巧，为了对 list 中的点进行向量计算，我们使用 complex() 函数将这些点变为复数形式。complex用法示例如下：
|
1 2 |
>>> 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%）：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
''' @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 |
