0939. Minimum Area Rectangle

题目信息

题号:

0939

难度:

Medium

主题:

平面点集、轴对齐矩形、最小面积

原题:

LeetCode 0939

重点:

矩形四边必须平行于坐标轴,四个顶点都要出现在给定点集中;若不存在矩形返回 0

题目重述

给定平面上的互不相同整数点数组 points。从中选择四个点作为矩形顶点,要求矩形的两条边平行于 x 轴,另外两条边平行于 y 轴,因此四点应由两个不同横坐标和两个不同纵坐标的全部组合构成。

请返回所有这种非零面积矩形中的最小面积;若无法选出任何轴对齐矩形,返回 0。

1 <= points.length <= 500,0 <= x_i, y_i <= 4 * 10^4,所有点互不相同。

自建示例

多组横坐标共享相同上下边:

输入:points = [[0,0],[0,2],[3,0],[3,2],[1,0],[1,2]]
输出:2
解释:横坐标 0 和 1、纵坐标 0 和 2 组成面积为 1 * 2 = 2 的矩形,比使用横坐标 1 和 3 或 0 和 3 的矩形更小。

点数不足以构成矩形:

输入:points = [[0,0],[0,2],[3,0]]
输出:0
解释:缺少顶点 [3,2],三个点不能组成轴对齐矩形,因此返回 0。