summaryrefslogtreecommitdiff
path: root/content/geometry/delaunay.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2024-08-06 16:54:13 +0200
committermzuenni <michi.zuendorf@gmail.com>2024-08-06 16:54:13 +0200
commit19436370fb48bc0a5e356d1ba713dc39b1a35d3a (patch)
tree42124647e993b50bc2b8af36090a0b0245a63992 /content/geometry/delaunay.cpp
parentd88debc398f18d4e3d1c53d221dffe3981f35e41 (diff)
upper case INF
Diffstat (limited to 'content/geometry/delaunay.cpp')
0 files changed, 0 insertions, 0 deletions
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-24 04:40:00 +0000
->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); } // 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);};