diff options
| author | MZuenni <michi.zuendorf@gmail.com> | 2023-03-01 13:41:30 +0100 |
|---|---|---|
| committer | MZuenni <michi.zuendorf@gmail.com> | 2023-03-01 13:41:30 +0100 |
| commit | 1074350c83504afe32cf4a14f43da82431d93d91 (patch) | |
| tree | 446ce991aa376c29c363a84778d6b53f15d1e35d /datastructures | |
| parent | 24f0c12468a2d66dcae1a3204d949b195daffb38 (diff) | |
made code easier to read
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/dynamicConvexHull.cpp | 18 |
1 files changed, 12 insertions, 6 deletions
diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index f88b2ad..7ea1977 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -17,12 +17,18 @@ struct HullDynamic : multiset<Line, less<>> { } 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)); - } + auto x = insert({m, b, 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)); + }} + while (x != begin() && prev(x)->p >= x->p) { + x--; + isect(x, erase(next(x))); + }} ll query(ll x) { auto l = *lower_bound(x); |
