competitive/algorithm/
convex_hull_trick.rs

1use std::collections::VecDeque;
2
3#[derive(Clone, Debug, Default, PartialEq, Eq)]
4pub struct ChtLine {
5    slope: i64,
6    intercept: i64,
7}
8impl ChtLine {
9    pub fn new(a: i64, b: i64) -> Self {
10        Self {
11            slope: a,
12            intercept: b,
13        }
14    }
15    pub fn value(&self, x: i64) -> i64 {
16        self.slope * x + self.intercept
17    }
18    pub fn check(&self, l1: &Self, l2: &Self) -> bool {
19        (l1.slope - self.slope) * (l2.intercept - l1.intercept)
20            >= (l1.intercept - self.intercept) * (l2.slope - l1.slope)
21    }
22}
23#[derive(Clone, Debug, Default)]
24pub struct ConvexHullTrick {
25    deq: VecDeque<ChtLine>,
26}
27impl ConvexHullTrick {
28    pub fn new() -> Self {
29        Default::default()
30    }
31    /// k-th add_line(a_k, b_k): a_k >= a_{k+1}
32    pub fn add_line(&mut self, a: i64, b: i64) {
33        let line = ChtLine::new(a, b);
34        while {
35            let k = self.deq.len();
36            k > 1 && self.deq[k - 2].check(&self.deq[k - 1], &line)
37        } {
38            self.deq.pop_back();
39        }
40        self.deq.push_back(line);
41    }
42    pub fn query(&mut self, x: i64) -> i64 {
43        while {
44            let k = self.deq.len();
45            k > 1 && self.deq[0].value(x) >= self.deq[1].value(x)
46        } {
47            self.deq.pop_front();
48        }
49        self.deq.front().unwrap().value(x)
50    }
51}
52
53// ConvexHullTrick verify: https://atcoder.jp/contests/dp/submissions/11341451
competitive/algorithm/convex_hull_trick.rs

competitive/algorithm/
convex_hull_trick.rs
