convex_hull_trick

クラス · Convex Hull Trick (monotone)

template <class T, class Comp = std::less<T>>
struct convex_hull_trick;

概要

Convex Hull Trick (monotone)

直線 $ax+b$ を傾き単調順に add し、任意の $x$ における最小値（または最大値）を 二分探索で求める。最小値は Comp = std::less<>（既定）で傾きを単調減少順、 最大値は Comp = std::greater<> で傾きを単調増加順に add すること。 クエリ get(x) の $x$ は任意の順で与えてよい。

メンバ関数