0939. Minimum Area Rectangle¶
题目信息¶
- 题号:
0939
- 难度:
Medium
- 主题:
平面点集、轴对齐矩形、最小面积
- 原题:
- 重点:
矩形四边必须平行于坐标轴,四个顶点都要出现在给定点集中;若不存在矩形返回
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。