LeetCode每日一题(963. Minimum Area Rectangle II)

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.

Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: points = [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000

Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000

Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0

Explanation: There is no possible rectangle to form from these points.

Constraints:

• 1 <= points.length <= 50
• points[i].length == 2
• 0 <= xi, yi <= 4 * 104
• All the given points are unique.

---

1. 从 points 中取出三个点 p1, p2, p3
2. p1 -> p2 生成向量 v1, p1 -> p3 生成向量 v2
3. 如果 v1 与 v2 相互垂直， 则从 p1 的基础上加上 v1 和 v2 得到 p4, 如果 p4 存在与 points 中， 则证明 p1, p2, p3, p4 可以组成一个矩形， 分别计算 v1 与 v2 的长度 l1, l2, l1 * l2 即为矩形面积

---

use std::collections::HashSet;

impl Solution {
    pub fn min_area_free_rect(points: Vec<Vec<i32>>) -> f64 {
        let point_set: HashSet<(i32, i32)> = points.iter().map(|l| (l[0], l[1])).collect();
        let mut ans = f64::MAX;
        for i in 0..points.len() {
            for j in i + 1..points.len() {
                for k in j + 1..points.len() {
                    let (x1, y1) = (points[i][0], points[i][1]);
                    let (x2, y2) = (points[j][0], points[j][1]);
                    let (x3, y3) = (points[k][0], points[k][1]);
                    let (vx1, vy1) = (x2 - x1, y2 - y1);
                    let (vx2, vy2) = (x3 - x1, y3 - y1);
                    if vx1 * vx2 + vy1 * vy2 == 0 {
                        let p4 = (x2 + vx2, y2 + vy2);
                        if point_set.contains(&p4) {
                            ans = ans.min(
                                (vx1.pow(2) as f64 + vy1.pow(2) as f64).sqrt()
                                    * (vx2.pow(2) as f64 + vy2.pow(2) as f64).sqrt(),
                            )
                        }
                    }
                }
            }
        }
        if ans == f64::MAX {
            0f64
        } else {
            ans
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33