This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "algorithm/convex_hull_trick.hpp"
直線の追加 (傾きの降順で)と $x$ における最小値クエリ ( $x$ は単調増加)を処理する。
直線 $y = ax + b$ を追加。傾きが降順で与えられると仮定。
$\min f_i(x)$ を求める。 与えられる $x$ は単調増加であると仮定。
#pragma once #include <cassert> #include <deque> #include <utility> namespace ebi { template <class T> struct convex_hull_trick { private: bool check(std::pair<T, T> a, std::pair<T, T> b, std::pair<T, T> c) { return (b.first - a.first) * (c.second - b.second) >= (c.first - b.first) * (b.second - a.second); } T f(std::pair<T, T> a, T x) { return a.first * x + a.second; } public: convex_hull_trick() = default; void add(T a, T b) { while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), {a, b})) { lines.pop_back(); } lines.emplace_back(a, b); } T min(T x) { assert(!lines.empty()); while (lines.size() >= 2 && f(lines[0], x) >= f(lines[1], x)) { lines.pop_front(); } return f(lines[0], x); } private: std::deque<std::pair<T, T>> lines; }; } // namespace ebi
#line 2 "algorithm/convex_hull_trick.hpp" #include <cassert> #include <deque> #include <utility> namespace ebi { template <class T> struct convex_hull_trick { private: bool check(std::pair<T, T> a, std::pair<T, T> b, std::pair<T, T> c) { return (b.first - a.first) * (c.second - b.second) >= (c.first - b.first) * (b.second - a.second); } T f(std::pair<T, T> a, T x) { return a.first * x + a.second; } public: convex_hull_trick() = default; void add(T a, T b) { while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), {a, b})) { lines.pop_back(); } lines.emplace_back(a, b); } T min(T x) { assert(!lines.empty()); while (lines.size() >= 2 && f(lines[0], x) >= f(lines[1], x)) { lines.pop_front(); } return f(lines[0], x); } private: std::deque<std::pair<T, T>> lines; }; } // namespace ebi