diff options
| -rw-r--r-- | datastructures/datastructures.tex | 2 | ||||
| -rw-r--r-- | datastructures/dynamicConvexHull.cpp | 59 | ||||
| -rw-r--r-- | tcr.pdf | bin | 646662 -> 662244 bytes |
3 files changed, 22 insertions, 39 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index dac8656..761a673 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -113,6 +113,8 @@ \sourcecode{datastructures/dynamicConvexHull.cpp} \end{algorithm} +\clearpage + \begin{algorithm}{Link-Cut-Tree} \begin{methods} \method{Constructor}{baut Wald auf}{n} diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index 5cdb12b..61ba976 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -1,50 +1,31 @@ -// 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; - } + mutable ll m, b, p; + bool operator<(const Line& o) const { return m < o.m; } + bool operator<(ll x) const { return p < 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); - } +struct HullDynamic : multiset<Line, less<>> { + // (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); } - // 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)); + bool isect(iterator x, iterator y) { + if (y == end()) {x->p = INF; return false;} + if (x->m == y->m) x->p = x->b > y->b ? INF : -INF; + else x->p = div(y->b - x->b, x->m - y->m); + return x->p >= y->p; } - // 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;}; + void add(ll m, ll b) { + auto z = insert({m, b, 0}), y = z++, x = y; + while (isect(y, z)) z = erase(z); + if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); + while ((y = x) != begin() && (--x)->p >= y->p) + isect(x, erase(y)); } - ll query(ll x) { // Laufzeit: O(log(n)) - auto l = *lower_bound((Line) {x, LLONG_MIN}); + ll query(ll x) { + auto l = *lower_bound(x); return l.m * x + l.b; } }; Binary files differ |