diff options
| -rw-r--r-- | content/datastructures/dynamicConvexHull.cpp | 2 | ||||
| -rw-r--r-- | content/datastructures/monotonicConvexHull.cpp | 6 | ||||
| -rw-r--r-- | tcr.pdf | bin | 691039 -> 691129 bytes | |||
| -rw-r--r-- | test/datastructures/dynamicConvexHull.cpp | 72 | ||||
| -rw-r--r-- | test/datastructures/monotonicConvexHull.cpp | 7 |
5 files changed, 77 insertions, 10 deletions
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index d669847..dfcfe0b 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -4,7 +4,7 @@ struct Line { bool operator<(ll x) const {return p < x;} }; -struct HullDynamic : multiset<Line, less<>> { +struct HullDynamic : multiset<Line, less<>> { // max über Geraden // (for doubles, use inf = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 119015e..e84ad86 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,4 +1,4 @@ -// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue +// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { ll m, c; @@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) { return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll c) { // Laufzeit O(1) amortisiert +void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } @@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // Laufzeit: O(1) amortisiert +ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); Binary files differdiff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp new file mode 100644 index 0000000..e0e56ef --- /dev/null +++ b/test/datastructures/dynamicConvexHull.cpp @@ -0,0 +1,72 @@ +#include "../util.h" +namespace dch { + constexpr ll INF = LL::INF; + #include <datastructures/dynamicConvexHull.cpp> +} + +struct Line { + ll m, c; + Line(ll m_, ll c_) : m(m_), c(c_) {} + ll operator()(ll x) {return m*x+c;} +}; + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer<int>(1, 100); + + vector<Line> naive; + + dch::HullDynamic hd; + for (int i = 0; i < n; i++) { + ll m = Random::integer<ll>(-range, range); + ll c = Random::integer<ll>(-range, range); + hd.add(m, c); + naive.emplace_back(m, c); + + for (int j = 0; j < 100; j++) { + ll x = Random::integer<ll>(-range, range); + + ll got = hd.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = max(expected, l(x)); + + if (got != expected) { + for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; + cerr << x << ": " << got << " " << expected << endl; + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + dch::HullDynamic hd; + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer<ll>(-1'000'000'000, 1'000'000'000); + ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000); + ll x = Random::integer<ll>(-1'000'000'000, 1'000'000'000); + + t.start(); + hd.add(m, c); + hash += hd.query(x); + t.stop(); + } + if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); + performance_test(); +} diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0d4e10d..4dafbd4 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -23,7 +23,7 @@ void stress_test(ll range) { MCH mch; for (ll m : ms) { - ll c = Random::integer<ll>(-1000, 1000); + ll c = Random::integer<ll>(-range, range); mch.add(m, c); naive.emplace_back(m, c); @@ -34,11 +34,6 @@ void stress_test(ll range) { ll expected = naive[0](x); for (auto l : naive) expected = min(expected, l(x)); - if (got != expected) { - for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; - cerr << x << ": " << got << " " << expected << endl; - } - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries++; } |