dsalgo/
convex_hull_monotone_chain.rs

1pub fn convex_hull(points: &[(i64, i64)]) -> Vec<(i64, i64)> {
2    let mut a = points.to_vec();
3
4    a.sort_unstable();
5
6    let is_ccw = |p0: &(i64, i64), p1: &(i64, i64), p2: &(i64, i64)| -> bool {
7        let (x0, y0) = p0;
8
9        let (x1, y1) = p1;
10
11        let (x2, y2) = p2;
12
13        (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) >= 0
14    };
15
16    let mut h = Vec::new();
17
18    // upper hull
19    for p in a.iter() {
20        let mut k = h.len();
21
22        while k >= 2 && is_ccw(&h[k - 2], &h[k - 1], p) {
23            h.pop();
24
25            k -= 1;
26        }
27
28        h.push(*p);
29    }
30
31    // lower hull
32    let m = h.len();
33
34    for p in a.iter().rev().skip(1) {
35        let mut k = h.len();
36
37        while k > m && is_ccw(&h[k - 2], &h[k - 1], p) {
38            h.pop();
39
40            k -= 1;
41        }
42
43        h.push(*p);
44    }
45
46    h.pop();
47
48    h
49}
50
51#[cfg(test)]
52
53mod tests {
54
55    #[test]
56
57    fn test() {}
58}
dsalgo/convex_hull_monotone_chain.rs

dsalgo/
convex_hull_monotone_chain.rs
