competitive::algorithm::convex_hull_trick

Struct ChtLine

pub struct ChtLine<T> {
    slope: T,
    intercept: T,
}

Fields§

§slope: T§intercept: T

Implementations§

Source §

impl<T> ChtLine<T>
where T: Copy + PartialOrd + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

Source

pub fn new(a: T, b: T) -> Self

Examples found in repository ?

crates/competitive/src/algorithm/convex_hull_trick.rs (line 80)

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    }

Source

pub fn value(&self, x: T) -> T

Examples found in repository ?

crates/competitive/src/algorithm/convex_hull_trick.rs (line 114)

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    }

Source

pub fn check(&self, l1: &Self, l2: &Self) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/convex_hull_trick.rs (line 87)

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    }