updated tcr

1 files changed, 45 insertions, 30 deletions

diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
index 042d26c..18a46d0 100644
--- a/datastructures/dynamicConvexHull.cpp
+++ b/datastructures/dynamicConvexHull.cpp
@@ -1,35 +1,50 @@
 // Upper Envelope, dynamisch.
 struct Line {
-    ll m, b;
-    mutable function<const Line*()> succ;
-    bool operator<(const Line& rhs) const {
-        if (rhs.b != LLONG_MIN) return m < rhs.m;
-        const Line* s = succ();
-        if (!s) return 0;
-        ll x = rhs.m;
-        return b - s->b < (s->m - m) * x;
-    }
+	ll m, b;
+	mutable function<const Line*()> succ;
+	bool operator<(const Line& rhs) const {
+		if (rhs.b != LLONG_MIN) 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, LLONG_MIN});
-        return l.m * x + l.b;
-    }
+	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);
+	}
+
+	// Variant 1: niklasb (2015)
+	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));
+	}
+
+	// Variant 2: barni120400 (2019)
+	void insert_line(ll m, ll b) {
+		auto y = insert({ m, b });
+		if (bad(y)) {erase(y); return;}
+		while (next(y) != end() && bad(next(y))) erase(next(y));
+		y->succ = [=] {return next(y) == end() ? 0 : &*next(y);};
+		while (y != begin() && bad(prev(y))) erase(prev(y));
+		if (y != begin()) prev(y)->succ = [=] {return &*y;};
+	}
+
+	ll query(ll x) { // Laufzeit: O(log(n)) 
+		auto l = *lower_bound((Line) {x, MIN});
+		return l.m * x + l.b;
+	}
 };