

LeetCode: 963. 最小面积矩形 II

• LeetCode: 963. 最小面积矩形 II
  • 1、题目描述
  • 2、解题思路

1、题目描述

给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

示例 1：

输入：[[1,2],[2,1],[1,0],[0,1]]
输出：2.00000
解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。

示例 2：

输入：[[0,1],[2,1],[1,1],[1,0],[2,0]]
输出：1.00000
解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。

示例 3：

输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0
解释：没法从这些点中组成任何矩形。

示例 4：

输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出：2.00000
解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。

提示：

• 1 <= points.length <= 50
• 0 <= points[i][0] <= 40000
• 0 <= points[i][1] <= 40000
• 所有的点都是不同的。
• 与真实值误差不超过 10^-5 的答案将视为正确结果。

2、解题思路

• 根据对角线进行归类，如果4个点想要组成一个矩形，肯定是对角线相同

• 按照对角线长度将一对点放入集合中

• 在集合中找出两组，

  • 首先判断是否是对角线
  • 然后判断边是否满足矩形，满足则更新矩形面积

from itertools import combinations
from collections import defaultdict
import math


class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        inf = float('inf')
        ans = inf

        diagonal = defaultdict(list)
        for (x1, y1), (x2, y2) in combinations(points, 2):
            diagonal[abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2].append([[x1, y1], [x2, y2]])

        remove_point = []
        for k in diagonal:
            if len(diagonal[k]) < 2:
                remove_point.append(k)

        for remove in remove_point:
            diagonal.pop(remove)

        for values in diagonal.values():
            for t1, t2 in combinations(values, 2):
                if len(set((x, y) for x, y in t1 + t2)) != 4:
                    continue
                # print(t1, t2)
                [x1, y1], [x2, y2] = t1
                [x3, y3], [x4, y4] = t2

                # 判断是否是对角线

                if (x1 + x2 == x3 + x4) and (y1 + y2 == y3 + y4):
                    edge1 = abs(x1 - x3) ** 2 + abs(y1 - y3) ** 2
                    edge2 = abs(x1 - x4) ** 2 + abs(y1 - y4) ** 2
                    edge3 = abs(x2 - x3) ** 2 + abs(y2 - y3) ** 2
                    edge4 = abs(x2 - x4) ** 2 + abs(y2 - y4) ** 2

                    if edge1 == edge4 and edge2 == edge3:
                        ans = min(ans, math.sqrt(edge1 * edge2))

        return ans if ans != inf else 0.0