难度:★★☆☆☆
类型:几何
方法:排列
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定在 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 的答案将视为正确结果。
解答
这道题没有巧办法,只能按部就班使用笨办法解决。
有以下几个知识点需要注意:
矩形的判定规则:对于一个右四个顶点组成的四边形,如果有三个角是直角,那么这个四边形是矩形。
向量垂直的法则:如果两个向量的点积(对应位置的乘积)为零,那么这两个向量垂直。
矩形的面积等于两条相邻边的欧式距离的乘积。
我们寻找所有四个点的排列情况,如果满足以上矩形的判定规则,则将该矩形的面积记录更新在结果ans中。
class Solution:
def minAreaFreeRect(self, points):
def vector(point1, point2):
(x1, y1), (x2, y2) = point1, point2
return x2-x1, y2-y1
def is_vertical(vector1, vector2):
if vector1 == (0, 0) or vector2 == (0, 0):
return False
(x1, y1), (x2, y2) = vector1, vector2
return x1 * x2 + y1 * y2 == 0
def dist(p1, p2):
(x1, y1), (x2, y2) = p1, p2
return ((x1-x2)**2+(y1-y2)**2)**0.5
ans = float("inf")
for p1 in points:
for p2 in points:
if p1 == p2:
continue
for p3 in points:
if p1 == p3 or p2 == p3:
continue
vector_p1p2, vector_p2p3 = vector(p1, p2), vector(p2, p3)
if not is_vertical(vector_p1p2, vector_p2p3):
continue
for p4 in points:
if p4 in [p1, p2, p3]:
continue
vector_p3p4, vector_p4p1 = vector(p3, p4), vector(p4, p1)
if is_vertical(vector_p1p2, vector_p4p1) and is_vertical(vector_p2p3, vector_p3p4):
area = dist(p1, p2) * dist(p2, p3)
ans = min(ans, area)
return 0 if ans == float("inf") else ans
s = Solution()
print(s.minAreaFreeRect([[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]))
如有疑问或建议,欢迎评论区留言~
有关更多力扣中等题的python解决方案,请移步力扣中等题解析
网友评论