Convex-Hull-Trick (src/Optimization/ConvexHullTrick.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-10-17 01:28:06+09:00
Include: #include "src/Optimization/ConvexHullTrick.hpp"
Link: View error logs on GitHub Actions

浮動小数点数も行けるはず

`ConvexHullTrick`

templateの第二引数で最大最小を指定. デフォルトは最小値取得.

メンバ関数	概要	計算量
`empty()`	何も直線を挿入していないなら true
`insert(k,m)`	直線 $y=kx+m$ を挿入	$O(\log n)$
`query_line(x)`	$x$ における最小値(最大値)をとる直線 $y=kx+m$ の係数 $(k,m)$ を返す.	$O(\log n)$
`query(x)`	$x$ における最小値(最大値) を返す	$O(\log n)$

`ConvexHullTrick_XY`

メンバ関数	概要	計算量
`empty()`	何も直線を挿入していないなら true
`insert(a,b)`	直線 $ax+by$ を挿入	$O(\log n)$
`get_min(x,y)`	$(x,y)$ における最小値を返す.	$O(\log n)$
`get_max(x,y)`	$(x,y)$ における最大値を返す.	$O(\log n)$

Verify

AtCoder Regular Contest 051 D - 長方形 (ax+by)
AtCoder Beginner Contest 244 Ex - Linear Maximization (ax+by)
Yandex Contest Алгоритм 2022 K. Stepwise subsequence (有理数クラスでac)

参考

Depends on

最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Verified with

Code

#pragma once
#include <limits>
#include <algorithm>
#include <set>
#include <array>
#include <cassert>
#include "src/Optimization/MinMaxEnum.hpp"
template <typename T, MinMaxEnum obj= MINIMIZE> class ConvexHullTrick {
 struct Line {
  T k, m;
  mutable T p;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(T x) const { return p < x; }
 };
 static constexpr T INF= std::numeric_limits<T>::max();
 static T lc_div(T a, T b) {
  if constexpr (std::is_integral_v<T>) return a / b - ((a ^ b) < 0 && a % b);
  else return a / b;
 }
 using ms= std::multiset<Line, std::less<>>;
 ms ls;
 bool insect(typename ms::iterator x, typename ms::iterator y) {
  if (y == ls.end()) return x->p= INF, false;
  if (x->k == y->k) x->p= (x->m > y->m ? INF : -INF);
  else x->p= lc_div(y->m - x->m, x->k - y->k);
  return x->p >= y->p;
 }
public:
 void insert(T k, T m) {
  if constexpr (obj == MINIMIZE) k= -k, m= -m;
  auto z= ls.insert({k, m, 0}), y= z++, x= y;
  while (insect(y, z)) z= ls.erase(z);
  if (x != ls.begin() && insect(--x, y)) insect(x, y= ls.erase(y));
  while ((y= x) != ls.begin() && (--x)->p >= y->p) insect(x, ls.erase(y));
 }
 bool empty() const { return ls.empty(); }
 std::array<T, 2> query_line(T x) const {
  assert(!ls.empty());
  auto l= ls.lower_bound(x);
  if constexpr (obj == MINIMIZE) return {-l->k, -l->m};
  else return {l->k, l->m};
 }
 T query(T x) const {
  auto [k, m]= query_line(x);
  return k * x + m;
 }
};
template <typename T> class ConvexHullTrick_XY {
 ConvexHullTrick<long double, MINIMIZE> cht_mn;
 ConvexHullTrick<long double, MAXIMIZE> cht_mx;
 T amx= std::numeric_limits<T>::lowest(), amn= std::numeric_limits<T>::max();
public:
 void insert(T a, T b) { cht_mn.insert(a, b), cht_mx.insert(a, b), amn= std::min(amn, a), amx= std::max(amx, a); }
 bool empty() const { return cht_mn.empty(); }
 T get_max(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::max(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mx.query_line(z) : cht_mn.query_line(z);
  return T(a) * x + T(b) * y;
 }
 T get_min(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::min(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mn.query_line(z) : cht_mx.query_line(z);
  return T(a) * x + T(b) * y;
 }
};

#line 2 "src/Optimization/ConvexHullTrick.hpp"
#include <limits>
#include <algorithm>
#include <set>
#include <array>
#include <cassert>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 8 "src/Optimization/ConvexHullTrick.hpp"
template <typename T, MinMaxEnum obj= MINIMIZE> class ConvexHullTrick {
 struct Line {
  T k, m;
  mutable T p;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(T x) const { return p < x; }
 };
 static constexpr T INF= std::numeric_limits<T>::max();
 static T lc_div(T a, T b) {
  if constexpr (std::is_integral_v<T>) return a / b - ((a ^ b) < 0 && a % b);
  else return a / b;
 }
 using ms= std::multiset<Line, std::less<>>;
 ms ls;
 bool insect(typename ms::iterator x, typename ms::iterator y) {
  if (y == ls.end()) return x->p= INF, false;
  if (x->k == y->k) x->p= (x->m > y->m ? INF : -INF);
  else x->p= lc_div(y->m - x->m, x->k - y->k);
  return x->p >= y->p;
 }
public:
 void insert(T k, T m) {
  if constexpr (obj == MINIMIZE) k= -k, m= -m;
  auto z= ls.insert({k, m, 0}), y= z++, x= y;
  while (insect(y, z)) z= ls.erase(z);
  if (x != ls.begin() && insect(--x, y)) insect(x, y= ls.erase(y));
  while ((y= x) != ls.begin() && (--x)->p >= y->p) insect(x, ls.erase(y));
 }
 bool empty() const { return ls.empty(); }
 std::array<T, 2> query_line(T x) const {
  assert(!ls.empty());
  auto l= ls.lower_bound(x);
  if constexpr (obj == MINIMIZE) return {-l->k, -l->m};
  else return {l->k, l->m};
 }
 T query(T x) const {
  auto [k, m]= query_line(x);
  return k * x + m;
 }
};
template <typename T> class ConvexHullTrick_XY {
 ConvexHullTrick<long double, MINIMIZE> cht_mn;
 ConvexHullTrick<long double, MAXIMIZE> cht_mx;
 T amx= std::numeric_limits<T>::lowest(), amn= std::numeric_limits<T>::max();
public:
 void insert(T a, T b) { cht_mn.insert(a, b), cht_mx.insert(a, b), amn= std::min(amn, a), amx= std::max(amx, a); }
 bool empty() const { return cht_mn.empty(); }
 T get_max(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::max(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mx.query_line(z) : cht_mn.query_line(z);
  return T(a) * x + T(b) * y;
 }
 T get_min(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::min(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mn.query_line(z) : cht_mx.query_line(z);
  return T(a) * x + T(b) * y;
 }
};