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
61
62

use crate::geometry::point::Point;
use std::collections::VecDeque;

pub fn convex_hull(ps: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
    let n = ps.len();

    let mut ps: Vec<Point<i64>> = ps.iter().map(|&(x, y)| Point::<i64>(x, y)).collect();

    ps.sort();

    let mut k = 0;
    let mut deque: VecDeque<Point<i64>> = VecDeque::new();

    for &pi in &ps {
        while k > 1 && (deque[k - 1] - deque[k - 2]).det(pi - deque[k - 1]) <= 0 {
            deque.pop_back();
            k -= 1;
        }
        deque.push_back(pi);
        k += 1;
    }

    let t = k;
    for i in (0..n - 1).rev() {
        let pi = ps[i];
        while k > t && (deque[k - 1] - deque[k - 2]).det(pi - deque[k - 1]) <= 0 {
            deque.pop_back();
            k -= 1;
        }
        deque.push_back(pi);
        k += 1;
    }

    let mut ret: Vec<(i64, i64)> = deque
        .into_iter()
        .take(k - 1)
        .map(|pair| (pair.0, pair.1))
        .collect();

    ret.sort_unstable();
    ret
}

#[cfg(test)]
mod test_convex_hull {
    use crate::geometry::convex_hull;

    #[test]
    fn it_works() {
        let ps = vec![(0, 0), (2, 2), (3, 1), (1, 4), (4, 4)];
        let hull = convex_hull::convex_hull(ps);
        assert_eq!(hull, vec![(0, 0), (1, 4), (3, 1), (4, 4)]);

        let ps = vec![(0, 0), (2, 2), (4, 4)];
        let hull = convex_hull::convex_hull(ps);
        assert_eq!(hull, vec![(0, 0), (4, 4)]);

        let ps = vec![(0, 0), (0, 1), (0, 2), (1, 1)];
        let hull = convex_hull::convex_hull(ps);
        assert_eq!(hull, vec![(0, 0), (0, 2), (1, 1)]);
    }
}