Line container (for max(ax + by) query)
(data-structure/line-container-2d.hpp)
Depends on
Verified with
Code
#pragma once
#include <algorithm>
using namespace std;
#include "line-container.hpp"
struct LineContainer2D {
using ld = long double;
using ll = long long;
ld Xmax, Xmin, Ymax, Ymin;
static constexpr ld INF = 4.1e18;
MinLineContainer<ld> minlc;
MaxLineContainer<ld> maxlc;
LineContainer2D() : Xmax(-INF), Xmin(INF), Ymax(-INF), Ymin(INF) {}
void add(ld x, ld y) {
Xmax = max(Xmax, x), Xmin = min(Xmin, x);
Ymax = max(Ymax, y), Ymin = min(Ymin, y);
minlc.add(y, x), maxlc.add(y, x);
}
ld max_ld(ld a, ld b) {
if (a == 0) return b * (b > 0 ? Ymax : Ymin);
if (b == 0) return a * (a > 0 ? Xmax : Xmin);
ld c = b / a;
if (a > 0) {
auto l = maxlc.lower_bound(c);
ld x = l->m, y = l->k;
return a * x + b * y;
} else {
auto l = minlc.lower_bound(c);
ld x = -l->m, y = -l->k;
return a * x + b * y;
}
}
ld min_ld(ld a, ld b) { return -max_ld(-a, -b); }
ll max_ll(ll a, ll b) { return round(clamp<ll>(max_ld(a, b), -INF, INF)); }
ll min_ll(ll a, ll b) { return round(clamp<ll>(min_ld(a, b), -INF, INF)); }
private:
ll round(ld a) { return a >= 0.0 ? a + 0.5 : a - 0.5; }
};
/**
* @brief Line container (for max(ax + by) query)
*/
#line 2 "data-structure/line-container-2d.hpp"
#include <algorithm>
using namespace std;
#line 2 "data-structure/line-container.hpp"
#include <cassert>
#include <set>
using namespace std;
enum Objective {
MAXIMIZE = +1,
MINIMIZE = -1,
};
template <typename T>
struct Line {
mutable T k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(T x) const { return p < x; }
};
template <typename T>
T lc_inf() {
return numeric_limits<T>::max();
}
template <>
long double lc_inf<long double>() {
return 1 / .0;
}
template <typename T>
T lc_div(T a, T b) {
return a / b - ((a ^ b) < 0 and a % b);
}
template <>
long double lc_div(long double a, long double b) {
return a / b;
};
template <typename T, Objective objective>
struct LineContainer : multiset<Line<T>, less<>> {
using super = multiset<Line<T>, less<>>;
using super::begin, super::end, super::insert, super::erase;
using super::empty, super::lower_bound;
const T inf = lc_inf<T>();
bool insect(typename super::iterator x, typename super::iterator y) {
if (y == 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;
}
void add(T k, T m) {
auto z = insert({k * objective, m * objective, 0}), y = z++, x = y;
while (insect(y, z)) z = erase(z);
if (x != begin() and insect(--x, y)) insect(x, y = erase(y));
while ((y = x) != begin() and (--x)->p >= y->p) insect(x, erase(y));
}
T query(T x) {
assert(!empty());
auto l = *lower_bound(x);
return (l.k * x + l.m) * objective;
}
};
template <typename T>
using MinLineContainer = LineContainer<T, Objective::MINIMIZE>;
template <typename T>
using MaxLineContainer = LineContainer<T, Objective::MAXIMIZE>;
/**
* @brief Line container
*/
#line 6 "data-structure/line-container-2d.hpp"
struct LineContainer2D {
using ld = long double;
using ll = long long;
ld Xmax, Xmin, Ymax, Ymin;
static constexpr ld INF = 4.1e18;
MinLineContainer<ld> minlc;
MaxLineContainer<ld> maxlc;
LineContainer2D() : Xmax(-INF), Xmin(INF), Ymax(-INF), Ymin(INF) {}
void add(ld x, ld y) {
Xmax = max(Xmax, x), Xmin = min(Xmin, x);
Ymax = max(Ymax, y), Ymin = min(Ymin, y);
minlc.add(y, x), maxlc.add(y, x);
}
ld max_ld(ld a, ld b) {
if (a == 0) return b * (b > 0 ? Ymax : Ymin);
if (b == 0) return a * (a > 0 ? Xmax : Xmin);
ld c = b / a;
if (a > 0) {
auto l = maxlc.lower_bound(c);
ld x = l->m, y = l->k;
return a * x + b * y;
} else {
auto l = minlc.lower_bound(c);
ld x = -l->m, y = -l->k;
return a * x + b * y;
}
}
ld min_ld(ld a, ld b) { return -max_ld(-a, -b); }
ll max_ll(ll a, ll b) { return round(clamp<ll>(max_ld(a, b), -INF, INF)); }
ll min_ll(ll a, ll b) { return round(clamp<ll>(min_ld(a, b), -INF, INF)); }
private:
ll round(ld a) { return a >= 0.0 ? a + 0.5 : a - 0.5; }
};
/**
* @brief Line container (for max(ax + by) query)
*/
Back to top page