LeetCode每日一题(587. Erect the Fence)

You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.

You are asked to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed.

Return the coordinates of trees that are exactly located on the fence perimeter.

Example 1:

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

Example 2:

Input: points = [[1,2],[2,2],[4,2]]
Output: [[4,2],[2,2],[1,2]]

Constraints:

• 1 <= points.length <= 3000
• points[i].length == 2
• 0 <= xi, yi <= 100
• All the given points are unique.

---

抄的 Jarvis Algorithm, 注意两点， orientation(p, q, r)因为是向量计算， 所以参数顺序很重要， 不要搞混了， 再就是官方的答案会导致死循环， 需要在共线检查里添加是否越过起始点的检查。剩下的大家看官方的解答吧

---

use std::collections::HashSet;

impl Solution {
    fn orientation(p: &[i32], q: &[i32], r: &[i32]) -> i32 {
        (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    }

    fn in_between(p: &[i32], i: &[i32], q: &[i32]) -> bool {
        let a = i[0] <= p[0] && i[0] >= q[0] || i[0] >= p[0] && i[0] <= q[0];
        let b = i[1] <= p[1] && i[1] >= q[1] || i[1] >= p[1] && i[1] <= q[1];
        a && b
    }
    pub fn outer_trees(trees: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        if trees.len() < 4 {
            return trees;
        }
        let mut hull = HashSet::new();
        let mut left_most = 0;
        for i in 0..trees.len() {
            if trees[i][0] < trees[left_most][0] {
                left_most = i;
            }
        }
        hull.insert(left_most);
        let mut p = left_most;
        loop {
            let mut q = (p + 1) % trees.len();
            for i in 0..trees.len() {
                if Solution::orientation(&trees[p], &trees[q], &trees[i]) > 0 {
                    q = i;
                }
            }
            hull.insert(q);
            let mut reached_begin = false;
            for i in 0..trees.len() {
                if i != p
                    && i != q
                    && Solution::orientation(&trees[p], &trees[q], &trees[i]) == 0
                    && Solution::in_between(&trees[p], &trees[i], &trees[q])
                {
                    if i == left_most {
                        reached_begin = true;
                    }
                    hull.insert(i);
                }
            }
            p = q;
            if p == left_most || reached_begin {
                break;
            }
        }
        trees
            .into_iter()
            .enumerate()
            .filter(|(i, _)| hull.contains(&i))
            .map(|(_, v)| v)
            .collect()
    }
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60