Convex Hull Trick
(algorithm/convex_hull_trick.hpp)

• View this file on GitHub
• Last update: 2023-07-05 21:52:12+09:00
• Include: #include "algorithm/convex_hull_trick.hpp"

説明

直線の追加 (傾きの降順で)と $x$ における最小値クエリ ( $x$ は単調増加)を処理する。

add(a, b)

直線 $y = ax + b$ を追加。傾きが降順で与えられると仮定。

get(x)

$\min f_i(x)$ を求める。 与えられる $x$ は単調増加であると仮定。

Verified with

• test/yuki/yuki_409.test.cpp

Code

#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

Back to top page