competitive/algorithm/
convex_hull_trick.rs

1use std::{
2    collections::VecDeque,
3    ops::{Add, Mul, Sub},
4};
5
6#[derive(Clone, Debug, Default, PartialEq, Eq)]
7pub struct ChtLine<T> {
8    slope: T,
9    intercept: T,
10}
11
12impl<T> ChtLine<T>
13where
14    T: Copy + PartialOrd + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
15{
16    pub fn new(a: T, b: T) -> Self {
17        Self {
18            slope: a,
19            intercept: b,
20        }
21    }
22    pub fn value(&self, x: T) -> T {
23        self.slope * x + self.intercept
24    }
25    pub fn check(&self, l1: &Self, l2: &Self) -> bool {
26        (l1.slope - self.slope) * (l2.intercept - l1.intercept)
27            >= (l1.intercept - self.intercept) * (l2.slope - l1.slope)
28    }
29}
30
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32enum ChtQueryMode {
33    Increasing,
34    Decreasing,
35    Any,
36}
37
38#[derive(Debug, Clone)]
39pub struct ConvexHullTrick<T> {
40    deq: VecDeque<ChtLine<T>>,
41    query_mode: ChtQueryMode,
42}
43
44impl<T> Default for ConvexHullTrick<T> {
45    fn default() -> Self {
46        Self {
47            deq: Default::default(),
48            query_mode: ChtQueryMode::Increasing,
49        }
50    }
51}
52
53impl<T> ConvexHullTrick<T>
54where
55    T: Copy + PartialOrd + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
56{
57    pub fn with_query_increasing() -> Self {
58        Self {
59            deq: Default::default(),
60            query_mode: ChtQueryMode::Increasing,
61        }
62    }
63
64    pub fn with_query_decreasing() -> Self {
65        Self {
66            deq: Default::default(),
67            query_mode: ChtQueryMode::Decreasing,
68        }
69    }
70
71    pub fn with_query_any() -> Self {
72        Self {
73            deq: Default::default(),
74            query_mode: ChtQueryMode::Any,
75        }
76    }
77
78    pub fn add_line(&mut self, a: T, b: T) {
79        if self.deq.is_empty() {
80            self.deq.push_back(ChtLine::new(a, b));
81        } else if let Some(l) = self.deq.back()
82            && l.slope >= a
83        {
84            let line = ChtLine::new(a, b);
85            while {
86                let k = self.deq.len();
87                k > 1 && self.deq[k - 2].check(&self.deq[k - 1], &line)
88            } {
89                self.deq.pop_back();
90            }
91            self.deq.push_back(line);
92        } else if let Some(l) = self.deq.front()
93            && l.slope <= a
94        {
95            let line = ChtLine::new(a, b);
96            while {
97                let k = self.deq.len();
98                k > 1 && line.check(&self.deq[0], &self.deq[1])
99            } {
100                self.deq.pop_front();
101            }
102            self.deq.push_front(line);
103        } else {
104            panic!("a must be monotonic");
105        }
106    }
107
108    pub fn query_min(&mut self, x: T) -> T {
109        assert!(!self.deq.is_empty(), "no lines added");
110        match self.query_mode {
111            ChtQueryMode::Increasing => {
112                while {
113                    let k = self.deq.len();
114                    k > 1 && self.deq[0].value(x) >= self.deq[1].value(x)
115                } {
116                    self.deq.pop_front();
117                }
118                self.deq.front().unwrap().value(x)
119            }
120            ChtQueryMode::Decreasing => {
121                while {
122                    let k = self.deq.len();
123                    k > 1 && self.deq[k - 1].value(x) >= self.deq[k - 2].value(x)
124                } {
125                    self.deq.pop_back();
126                }
127                self.deq.back().unwrap().value(x)
128            }
129            ChtQueryMode::Any => {
130                let mut l = 0;
131                let mut r = self.deq.len() - 1;
132                while l < r {
133                    let m = (l + r) / 2;
134                    if self.deq[m].value(x) >= self.deq[m + 1].value(x) {
135                        l = m + 1;
136                    } else {
137                        r = m;
138                    }
139                }
140                self.deq[l].value(x)
141            }
142        }
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    use super::*;
149    use crate::tools::Xorshift;
150    const A: i64 = 1_000_000_000;
151
152    #[test]
153    fn test_convex_hull_trick() {
154        let mut rng = Xorshift::default();
155        for _ in 0..200 {
156            let q = rng.random(1..200);
157            let mut lines: Vec<_> = rng.random_iter((-A..=A, -A..=A)).take(q).collect();
158            let mut xs: Vec<_> = rng.random_iter(-A..=A).take(q).collect();
159            for lty in 0..2 {
160                if lty == 0 {
161                    lines.sort_unstable_by_key(|&(a, _)| -a);
162                } else {
163                    lines.sort_unstable_by_key(|&(a, _)| a);
164                }
165                for qty in 0..3 {
166                    let mut cht = if qty == 0 {
167                        rng.shuffle(&mut xs);
168                        ConvexHullTrick::with_query_any()
169                    } else if qty == 1 {
170                        xs.sort_unstable_by_key(|&x| -x);
171                        ConvexHullTrick::with_query_decreasing()
172                    } else {
173                        xs.sort_unstable();
174                        ConvexHullTrick::with_query_increasing()
175                    };
176                    for (i, (&(a, b), &x)) in lines.iter().zip(&xs).enumerate() {
177                        cht.add_line(a, b);
178                        let result = cht.query_min(x);
179                        let expected = lines[..=i].iter().map(|&(a, b)| a * x + b).min().unwrap();
180                        assert_eq!(result, expected);
181                    }
182                }
183            }
184        }
185    }
186}
competitive/algorithm/convex_hull_trick.rs

competitive/algorithm/
convex_hull_trick.rs
