力扣第 116 场周赛第 3 题
题目
给你一个 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。
返回由这些点形成的任意矩形的最小面积，矩形的边 不一定 平行于 X 轴和 Y 轴。如果不存在这样的矩形，则返回 0。
答案只需在10-5 的误差范围内即可被视作正确答案。
示例 1：
输入： points = [[1,2],[2,1],[1,0],[0,1]]
输出： 2.00000
解释： 最小面积矩形由 [1,2]、[2,1]、[1,0]、[0,1] 组成，其面积为 2。
示例 2：
输入： points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
输出： 1.00000
解释： 最小面积矩形由 [1,0]、[1,1]、[2,1]、[2,0] 组成，其面积为 1。
示例 3：
输入： points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
输出： 0
解释： 无法由这些点组成任何矩形。
提示：
1 <= points.length <= 50points[i].length == 20 <= xi, yi <= 4 * 104- 所有给定的点都是 唯一 的。
分析
#1
- 最简单的就是遍历三个点，判断形成的两条边是否垂直，并判断对应的第四个点是否存在
- 判断垂直可以用内积，计算面积可以用外积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def dot(u,v): # u·v，点乘（内积）
return u[0]*v[0]+u[1]*v[1]
def cross(u,v): # u X v，叉乘（外积），逆正顺负
return u[0]*v[1]-u[1]*v[0]
class Solution:
def minAreaFreeRect(self, points: List[List[int]]) -> float:
vis = {(x,y) for x,y in points}
res = inf
for p1, p2, p3 in permutations(points, 3):
p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]
if p4 in vis:
v1 = (p2[0] - p1[0], p2[1] - p1[1])
v2 = (p3[0] - p1[0], p3[1] - p1[1])
if dot(v1,v2)==0:
area = abs(cross(v1,v2))
if area < res:
res = area
return res if res < inf else 0
|
687 ms
#2
- 还可以按对角线分组，矩形的两条对角线满足：
- 同一组内，夹角更小的两条对角线组成的矩形面积更小
- 因此组内极角排序，计算相邻对角线的外积即可
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def cross(u,v): # u X v，叉乘（外积），逆正顺负
return u[0]*v[1]-u[1]*v[0]
class Solution:
def minAreaFreeRect(self, points: List[List[int]]) -> float:
n = len(points)
d = defaultdict(list)
for i in range(n):
for j in range(i+1,n):
u,v = sorted([points[i],points[j]])
mid = (u[0]+v[0],u[1]+v[1])
p = [v[0]-u[0],v[1]-u[1]]
r = p[0]**2+p[1]**2
d[(mid,r)].append(p)
res = inf
for A in d.values():
A.sort(key=lambda u: atan2(u[1],u[0]))
if len(A)>1:
for u,v in zip(A,A[1:]+A[:1]):
res = min(res,abs(cross(u,v)))
return res/2 if res<inf else 0
|
54 ms