0963. Minimum Area Rectangle II

题目信息

题号:

0963

难度:

Medium

主题:

平面点集、任意方向矩形、最小面积

原题:

LeetCode 0963

重点:

矩形可以旋转,不要求边平行于坐标轴;四个顶点都必须来自输入,返回最小非零面积,不存在时返回 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
解释:只有三个点,无法选出矩形所需的四个不同顶点。