From 7e24d9d392aff890981f13c299b283189d94a75d Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Fri, 15 Mar 2024 01:25:09 +0100 Subject: too many changes for one commit - simplify envelope code - add more files as optional - allow compiling optional without editing tcr.tex - formatting changes --- datastructures/monotonicConvexHull.cpp | 43 +++++++++++++++++----------------- 1 file changed, 21 insertions(+), 22 deletions(-) (limited to 'datastructures/monotonicConvexHull.cpp') diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 44bff83..e7b9b3e 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,26 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. -struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} -}; +struct Envelope { + struct Line { + ll m, b; + ll operator()(ll x) { return m*x+b; } + }; -vector ls; -int ptr = 0; + vector ls; + int ptr = 0; -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); -} + static 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 - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { - ls.pop_back(); + void add(ll m, ll b) { + while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) { + ls.pop_back(); + } + ls.push_back({m, b}); + ptr = min(ptr, sz(ls) - 1); } - ls.push_back({m, b}); - ptr = min(ptr, sz(ls) - 1); -} -ll query(ll x) { // Laufzeit: O(1) amortisiert - 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 + ll query(ll x) { + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); + } +}; -- cgit v1.2.3