sotanishy's code snippets for competitive programming
#include "data-structure/cht/convex_hull_trick.hpp"
Convex hull trick は,直線集合 $L$ への追加クエリと最小値クエリを効率的に行う手法である.
この実装では,追加する直線の傾きが単調非増加である必要がある.傾きに単調性がないときは平衡二分探索木を用いた CHT または Li Chao tree を使用せよ.
空間計算量: $O(n)$
void add(T a, T b)
T get(T x)
#pragma once
#include <algorithm>
#include <deque>
#include <utility>
#include <vector>
template <typename T>
class ConvexHullTrick {
public:
void add(T a, T b) {
Line line(a, b);
while (lines.size() >= 2 &&
check(lines[lines.size() - 2], lines.back(), line)) {
lines.pop_back();
}
lines.push_back(line);
}
T get(T x) {
while (lines.size() >= 2 && lines.front()(x) > lines[1](x)) {
lines.pop_front();
}
return lines.front()(x);
}
private:
struct Line {
T a, b;
Line(T a, T b) : a(a), b(b) {}
T operator()(T x) const { return a * x + b; }
};
std::deque<Line> lines;
static bool check(Line l1, Line l2, Line l3) {
if (l1.a == l2.a) return l2.b >= l1.b;
if (l2.a == l3.a) return l2.b >= l3.b;
return 1.0 * (l2.b - l1.b) / (l2.a - l1.a) <=
1.0 * (l3.b - l2.b) / (l3.a - l2.a);
}
};
#line 2 "data-structure/cht/convex_hull_trick.hpp"
#include <algorithm>
#include <deque>
#include <utility>
#include <vector>
template <typename T>
class ConvexHullTrick {
public:
void add(T a, T b) {
Line line(a, b);
while (lines.size() >= 2 &&
check(lines[lines.size() - 2], lines.back(), line)) {
lines.pop_back();
}
lines.push_back(line);
}
T get(T x) {
while (lines.size() >= 2 && lines.front()(x) > lines[1](x)) {
lines.pop_front();
}
return lines.front()(x);
}
private:
struct Line {
T a, b;
Line(T a, T b) : a(a), b(b) {}
T operator()(T x) const { return a * x + b; }
};
std::deque<Line> lines;
static bool check(Line l1, Line l2, Line l3) {
if (l1.a == l2.a) return l2.b >= l1.b;
if (l2.a == l3.a) return l2.b >= l3.b;
return 1.0 * (l2.b - l1.b) / (l2.a - l1.a) <=
1.0 * (l3.b - l2.b) / (l3.a - l2.a);
}
};