haar_lib/geom_int/
convex_hull.rs

1//! 凸包
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/static_convex_hull>
5
6use crate::geom_int::*;
7
8/// 凸包の上半分か下半分かを指定する
9#[derive(Clone, Copy, PartialEq, Eq)]
10pub enum Hull {
11    /// 上半分
12    Upper,
13    /// 下半分
14    Lower,
15}
16
17/// 上半分/下半分の凸包を求める
18pub fn half_hull(mut ps: Vec<VectorInt>, hull: Hull) -> Vec<VectorInt> {
19    if ps.is_empty() {
20        return vec![];
21    }
22
23    ps.sort_by(|p, q| (p.x, p.y).cmp(&(q.x, q.y)));
24
25    if hull == Hull::Upper {
26        ps.reverse();
27    }
28
29    let mut ret = vec![*ps.last().unwrap()];
30    ps.pop();
31
32    while let Some(s) = ps.pop() {
33        if ret.len() == 1 {
34            ret.push(s);
35        } else {
36            let p = ret[ret.len() - 2];
37            let q = *ret.last().unwrap();
38
39            if (q - p).cross(s - p) < 0 {
40                ret.push(s);
41            } else {
42                ret.pop();
43                ps.push(s);
44            }
45        }
46    }
47
48    ret
49}
50
51/// 凸包を求める
52pub fn convex_hull(ps: Vec<VectorInt>) -> Vec<VectorInt> {
53    let mut ret = half_hull(ps.clone(), Hull::Upper);
54    let lower = half_hull(ps, Hull::Lower);
55    ret.extend(lower);
56    ret.dedup();
57
58    if let Some(first) = ret.first().cloned() {
59        while ret.len() > 1 && ret.last().is_some_and(|p| p == &first) {
60            ret.pop();
61        }
62    }
63
64    ret
65}
haar_lib/geom_int/convex_hull.rs

haar_lib/geom_int/
convex_hull.rs
