0963. Minimum Area Rectangle II¶
题目信息¶
- 题号:
0963
- 难度:
Medium
- 主题:
平面点集、任意方向矩形、最小面积
- 原题:
- 重点:
矩形可以旋转,不要求边平行于坐标轴;四个顶点都必须来自输入,返回最小非零面积,不存在时返回
0
题目重述¶
给定平面上互不相同的整数点数组 points。从中选择四个点作为一个非退化矩形的四个顶点,矩形可以采用任意方向,不要求边与坐标轴平行。
请返回所有可构成矩形中的最小面积。若无法从给定点中构成任何非零面积矩形,返回 0。答案与真实值的误差在 10^-5 以内即可接受。
1 <= points.length <= 50,0 <= x_i, y_i <= 4 * 10^4,所有点互不相同。
自建示例¶
四点组成倾斜矩形:
输入:points = [[1,1],[3,2],[2,4],[0,3]]
输出:5.0
解释:从 [1,1] 出发的两条相邻边向量为 (2,1) 和 (-1,2),二者点积为 0、长度都为 sqrt(5),因此四点组成面积为 5 的正方形。
点集无法构成矩形:
输入:points = [[0,0],[1,1],[2,0]]
输出:0.0
解释:只有三个点,无法选出矩形所需的四个不同顶点。