diff options
| -rw-r--r-- | test/datastructures/dynamicConvexHull.cpp | 5 | ||||
| -rw-r--r-- | test/datastructures/dynamicConvexHull.lichao.cpp | 38 |
2 files changed, 38 insertions, 5 deletions
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index e0e56ef..f163397 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -31,11 +31,6 @@ void stress_test(ll range) { 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++; } diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp new file mode 100644 index 0000000..6ab55f0 --- /dev/null +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -0,0 +1,38 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +constexpr ll inf = LL::INF; +#include <datastructures/dynamicConvexHull.cpp> +#include <datastructures/lichao.cpp> + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer<int>(1, 100); + xs = Random::distinct(n, -range, range); + sort(all(xs)); + + HullDynamic hd; + Lichao lichao; + for (int i = 0; i < 1000; i++) { + ll m = Random::integer<ll>(-range, range); + ll c = Random::integer<ll>(-range, range); + hd.add(m, c); + lichao.insert({-m, -c}); + + for (ll x : xs) { + ll gotA = hd.query(x); + ll gotB = -lichao.query(x); + + if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL; + queries++; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); +} |