diff options
Diffstat (limited to 'content/datastructures/dynamicConvexHull.cpp')
| -rw-r--r-- | content/datastructures/dynamicConvexHull.cpp | 22 |
1 files changed, 10 insertions, 12 deletions
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 63e0e13..3e4020e 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,16 +1,16 @@ struct Line { mutable ll m, c, p; - bool operator<(const Line& o) const {return m < o.m;} - bool operator<(ll x) const {return p < x;} + bool operator<(const Line& o) const { return m > o.m; } + bool operator<(ll x) const { return p < x; } }; -struct HullDynamic : multiset<Line, less<>> { // max über Geraden +struct HullDynamic : multiset<Line, less<>> { // min über Geraden // (for doubles, use INF = 1/.0, div(a,c) = a/c) - ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);} + ll div(ll a, ll c) { return a / c - ((a ^ c) < 0 && a % c); } bool isect(iterator x, iterator y) { - if (y == end()) {x->p = INF; return false;} - if (x->m == y->m) x->p = x->c > y->c ? INF : -INF; + if (y == end()) { x->p = INF; return false; } + if (x->m == y->m) x->p = x->c < y->c ? INF : -INF; else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; } @@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden auto x = insert({m, c, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { - x--; - if (isect(x, next(x))) { - erase(next(x)); - isect(x, next(x)); - }} + --x; + while (isect(x, next(x))) erase(next(x)); + } while (x != begin() && prev(x)->p >= x->p) { - x--; + --x; isect(x, erase(next(x))); }} |