From f209418070050d4310a19191e3cd771760e5b521 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 28 Aug 2023 16:39:50 +0200 Subject: changed convex hull --- datastructures/dynamicConvexHull.cpp | 1 - datastructures/monotonicConvexHull.cpp | 30 ++++++++++++++++-------------- 2 files changed, 16 insertions(+), 15 deletions(-) (limited to 'datastructures') diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index 7ea1977..d669847 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -6,7 +6,6 @@ struct Line { struct HullDynamic : multiset> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) - static constexpr ll INF = LLONG_MAX; ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} bool isect(iterator x, iterator y) { diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 0049b3d..44bff83 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -1,25 +1,27 @@ // Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. -vector ms, bs; +struct Line { + ll m, b; + ll operator()(ll x) {return m*x+b;} +}; + +vector ls; int ptr = 0; -bool bad(int l1, int l2, int l3) { - return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < - (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); +bool bad(Line l1, Line l2, Line l3) { + return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); } void add(ll m, ll b) { // Laufzeit O(1) amortisiert - ms.push_back(m); bs.push_back(b); - while (sz(ms) >= 3 && bad(sz(ms)-3, sz(ms)-2, sz(ms)-1)) { - ms.erase(ms.end() - 2); bs.erase(bs.end() - 2); + while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { + ls.pop_back(); } - ptr = min(ptr, sz(ms) - 1); + ls.push_back({m, b}); + ptr = min(ptr, sz(ls) - 1); } -ll get(int idx, ll x) {return ms[idx] * x + bs[idx];} - ll query(ll x) { // Laufzeit: O(1) amortisiert - if (ptr >= sz(ms)) ptr = sz(ms) - 1; - while (ptr < sz(ms)-1 && get(ptr + 1, x) < get(ptr, x)) ptr++; - return get(ptr, x); -} + ptr = min(ptr, sz(ls) - 1); + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); +} \ No newline at end of file -- cgit v1.2.3