Adding dynamic variant of convex hull optimization.

1 files changed, 35 insertions, 0 deletions

diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..9ccf220
--- /dev/null
+++ b/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,35 @@
+// Upper Envelope, dynamisch.
+struct Line {
+    ll m, b;
+    mutable function<const Line*()> succ;
+    bool operator<(const Line& rhs) const {
+        if (rhs.b != is_query) return m < rhs.m;
+        const Line* s = succ();
+        if (!s) return 0;
+        ll x = rhs.m;
+        return b - s->b < (s->m - m) * x;
+    }
+};
+struct HullDynamic : public multiset<Line> {
+    bool bad(iterator y) {
+        auto z = next(y);
+        if (y == begin()) {
+            if (z == end()) return 0;
+            return y->m == z->m && y->b <= z->b;
+        }
+        auto x = prev(y);
+        if (z == end()) return y->m == x->m && y->b <= x->b;
+        return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
+    }
+    void insert_line(ll m, ll b) { // Laufzeit: O(log(n))
+        auto y = insert({ m, b });
+        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
+        if (bad(y)) { erase(y); return; }
+        while (next(y) != end() && bad(next(y))) erase(next(y));
+        while (y != begin() && bad(prev(y))) erase(prev(y));
+    }
+    ll query(ll x) { // Laufzeit: O(log(n))
+        auto l = *lower_bound((Line) { x, -(1LL<<62) });
+        return l.m * x + l.b;
+    }
+};