diff options
Diffstat (limited to 'test/datastructures/monotonicConvexHull.cpp')
| -rw-r--r-- | test/datastructures/monotonicConvexHull.cpp | 28 |
1 files changed, 13 insertions, 15 deletions
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0415068..98d74f8 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -1,7 +1,5 @@ #include "../util.h" -struct MCH { - #include <datastructures/monotonicConvexHull.cpp> -}; +#include <datastructures/monotonicConvexHull.cpp> struct Line { ll m, c; @@ -14,12 +12,12 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); auto ms = Random::integers<ll>(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct<ll>(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -27,12 +25,12 @@ void stress_test(ll range) { } auto xs = Random::integers<ll>(n*100, -range*n, range*n); - sort(all(xs)); + ranges::sort(xs); int i = 0; vector<Line> naive; - MCH mch; + Envelope mch; for (int k = 0; k < n; k++) { ll m = ms[k]; ll c = cs[k]; @@ -60,12 +58,12 @@ void stress_test_independent(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); auto ms = Random::integers<ll>(n, -range, range); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto cs = ms; for (int l = 0, r = 0; l < n;) { while (r < n && ms[l] == ms[r]) r++; auto tmp = Random::distinct<ll>(r - l, -range, range); - sort(all(tmp), greater<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -74,7 +72,7 @@ void stress_test_independent(ll range) { vector<Line> naive; - MCH mch; + Envelope mch; for (int i = 0; i < n; i++) { ll m = ms[i]; ll c = cs[i]; @@ -83,7 +81,7 @@ void stress_test_independent(ll range) { naive.emplace_back(m, c); auto xs = Random::integers<ll>(100, -range, range); - sort(all(xs)); + ranges::sort(xs); auto tmp = mch; for (auto x : xs) { @@ -103,17 +101,17 @@ constexpr int N = 1'000'000; void performance_test() { timer t; auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(ms), greater<>{}); + ranges::sort(ms | views::reverse); auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); - MCH mch; + ranges::sort(xs); + Envelope mch; hash_t hash = 0; for (int operations = 0; operations < N; operations++) { ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000); ll m = ms[operations]; ll x = xs[operations]; - + t.start(); mch.add(m, c); hash += mch.query(x); |