library2
This documentation is automatically generated by competitive-verifier/competitive-verifier
geometry/convex-hull-trick.hpp
- View this file on GitHub
- Last update: 2025-09-03 17:27:43+02:00
- Include:
#include "geometry/convex-hull-trick.hpp" - Link: https://goodstudyqaq.notion.site/Convex-hull-trick-263c5c0415c48017bc01c34c3d8d0bc0
- Link: https://noshi91.hatenablog.com/entry/2021/03/23/200810
Depends on
Verified with
Code
#include <bits/stdc++.h>
#include <algorithm>
#include <limits>
#include <type_traits>
#include "./base.hpp"
#include "./point.hpp"
// https://goodstudyqaq.notion.site/Convex-hull-trick-263c5c0415c48017bc01c34c3d8d0bc0
using namespace std;
namespace geometry {
template <typename T>
struct ConvexHullTrick {
struct Line {
T a, b, r;
bool operator<(Line &l) { return pair(a, b) > pair(l.a, l.b); }
bool operator<(T x) { return r < x; }
};
ConvexHullTrick() = default;
ConvexHullTrick(vector<Line> &lines, bool is_min = true) : lines(lines), is_min(is_min) {
int n = lines.size();
if (!is_min) {
for (int i = 0; i < n; i++) {
lines[i].a *= -1;
lines[i].b *= -1;
}
}
if (!ranges::is_sorted(lines, less())) {
ranges::sort(lines, less());
}
// 求上凸包
const T inf = numeric_limits<T>::max();
vector<int> stk;
stk.push_back(0);
lines[stk.back()].r = inf;
for (int i = 1; i < n; i++) {
for (; !stk.empty(); stk.pop_back()) {
if (lines[stk.back()].a == lines[i].a) {
continue;
}
// https://noshi91.hatenablog.com/entry/2021/03/23/200810
T da = lines[stk.back()].a - lines[i].a;
T db = lines[i].b - lines[stk.back()].b;
lines[stk.back()].r = db / da - ((db < 0) & ((db % da) != 0));
if (stk.size() == 1 || lines[stk.back()].r > lines[stk[stk.size() - 2]].r) break;
}
stk.push_back(i);
lines[i].r = inf;
}
for (auto it : stk) {
convex.emplace_back(lines[it]);
}
}
T query(T x) {
assert(!convex.empty());
auto idx = lower_bound(convex.begin(), convex.end(), x) - convex.begin();
return get_y(idx, x);
}
private:
bool is_min;
vector<Line> convex, lines;
T get_y(int idx, T x) {
return convex[idx].a * x + convex[idx].b;
}
};
} // namespace geometry
#line 1 "geometry/convex-hull-trick.hpp"
#include <bits/stdc++.h>
#line 6 "geometry/convex-hull-trick.hpp"
#include <type_traits>
#line 3 "geometry/base.hpp"
using namespace std;
namespace geometry {
template <typename T>
const constexpr T EPS = static_cast<T>(1e-8);
template <typename T>
const constexpr T PI = acos(static_cast<T>(-1));
template <typename T>
inline int sign(const T &r) {
return r < -EPS<T> ? -1 : r > EPS<T> ? 1
: 0;
}
template <typename T>
inline bool equals(const T &a, const T &b) { return sign(a - b) == 0; }
} // namespace geometry
#line 2 "geometry/point.hpp"
#line 4 "geometry/point.hpp"
using namespace std;
namespace geometry {
template <typename T>
struct TPoint {
T x, y;
int id;
TPoint() : x(0), y(0), id(-1) {}
TPoint(const T& x_, const T& y_) : x(x_), y(y_), id(-1) {}
TPoint(const T& x_, const T& y_, int id_) : x(x_), y(y_), id(id_) {}
static constexpr T eps = static_cast<T>(1e-9);
inline TPoint operator+(const TPoint& rhs) const { return TPoint(x + rhs.x, y + rhs.y); }
inline TPoint operator-(const TPoint& rhs) const { return TPoint(x - rhs.x, y - rhs.y); }
inline TPoint operator*(const T& rhs) const { return TPoint(x * rhs, y * rhs); }
inline TPoint operator/(const T& rhs) const { return TPoint(x / rhs, y / rhs); }
friend T smul(const TPoint& a, const TPoint& b) {
// 点积
return a.x * b.x + a.y * b.y;
}
friend T vmul(const TPoint& a, const TPoint& b) {
// 叉积
return a.x * b.y - a.y * b.x;
}
inline T abs2() const {
return x * x + y * y;
}
inline bool operator<(const TPoint& rhs) const {
return (y < rhs.y || (y == rhs.y && x < rhs.x));
}
};
template <typename T>
string to_string(const TPoint<T>& p) {
return "(" + std::to_string(p.x) + ", " + std::to_string(p.y) + ")";
}
template <typename T>
bool compare_by_polar_angle(const TPoint<T>& a, const TPoint<T>& b) {
T x = vmul(a, b);
return x == 0 ? (a.abs2() < b.abs2()) : x > 0;
}
} // namespace geometry
#line 10 "geometry/convex-hull-trick.hpp"
// https://goodstudyqaq.notion.site/Convex-hull-trick-263c5c0415c48017bc01c34c3d8d0bc0
using namespace std;
namespace geometry {
template <typename T>
struct ConvexHullTrick {
struct Line {
T a, b, r;
bool operator<(Line &l) { return pair(a, b) > pair(l.a, l.b); }
bool operator<(T x) { return r < x; }
};
ConvexHullTrick() = default;
ConvexHullTrick(vector<Line> &lines, bool is_min = true) : lines(lines), is_min(is_min) {
int n = lines.size();
if (!is_min) {
for (int i = 0; i < n; i++) {
lines[i].a *= -1;
lines[i].b *= -1;
}
}
if (!ranges::is_sorted(lines, less())) {
ranges::sort(lines, less());
}
// 求上凸包
const T inf = numeric_limits<T>::max();
vector<int> stk;
stk.push_back(0);
lines[stk.back()].r = inf;
for (int i = 1; i < n; i++) {
for (; !stk.empty(); stk.pop_back()) {
if (lines[stk.back()].a == lines[i].a) {
continue;
}
// https://noshi91.hatenablog.com/entry/2021/03/23/200810
T da = lines[stk.back()].a - lines[i].a;
T db = lines[i].b - lines[stk.back()].b;
lines[stk.back()].r = db / da - ((db < 0) & ((db % da) != 0));
if (stk.size() == 1 || lines[stk.back()].r > lines[stk[stk.size() - 2]].r) break;
}
stk.push_back(i);
lines[i].r = inf;
}
for (auto it : stk) {
convex.emplace_back(lines[it]);
}
}
T query(T x) {
assert(!convex.empty());
auto idx = lower_bound(convex.begin(), convex.end(), x) - convex.begin();
return get_y(idx, x);
}
private:
bool is_min;
vector<Line> convex, lines;
T get_y(int idx, T x) {
return convex[idx].a * x + convex[idx].b;
}
};
} // namespace geometry