more testcases

4 files changed, 100 insertions, 19 deletions

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 44bff83..119015e 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,27 @@
-// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
+// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
 struct Line {
-	ll m, b;
-	ll operator()(ll x) {return m*x+b;}
+	ll m, c;
+	ll operator()(ll x) {return m*x+c;}
 };
 
 vector<Line> ls;
-int ptr = 0;
+ll ptr = 0;
 
 bool bad(Line l1, Line l2, Line l3) {
-	return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
+	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
 }
 
-void add(ll m, ll b) { // Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
+void add(ll m, ll c) { // Laufzeit O(1) amortisiert
+	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
 		ls.pop_back();
 	}
-	ls.push_back({m, b});
+	ls.push_back({m, c});
 	ptr = min(ptr, sz(ls) - 1);
 }
 
 ll query(ll x) { // Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
-	while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
 }
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 1cb888a..48a07d7 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
index acd048f..c8a56a3 100644
--- a/test/datastructures/lichao.cpp
+++ b/test/datastructures/lichao.cpp
@@ -2,11 +2,11 @@
 constexpr ll inf = LL::INF;
 #include <datastructures/lichao.cpp>
 
-void stress_test() {
+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<ll>(n, -1000, 1000);
+		xs = Random::distinct<ll>(n, -range, range);
 		sort(all(xs));
 
 		vector<ll> naive(n, inf);
@@ -15,9 +15,9 @@ void stress_test() {
 		for (int operations = 0; operations < 1000; operations++) {
 			{
 				ll m = Random::integer<ll>(-100, 100);
-				ll c = Random::integer<ll>(-1000, 1000);
-				ll l = Random::integer<ll>(-1000, 1000);
-				ll r = Random::integer<ll>(-1000, 1000);
+				ll c = Random::integer<ll>(-range, range);
+				ll l = Random::integer<ll>(-range, range);
+				ll r = Random::integer<ll>(-range, range);
 				Fun f{m, c};
 
 				tree.segmentInsert(f, l, r);
@@ -31,11 +31,11 @@ void stress_test() {
 				ll got = tree.query(xs[i]);
 				ll expected = naive[i];
 				if (got != expected) cerr << xs[i] << endl;
-				if (got != expected) cerr << "  got: " << got << ", expected: " << expected << FAIL;
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 			}
 		}
 	}
-	cerr << "  tested random queries: " << queries << endl;
+	cerr << "tested random queries: " << queries << endl;
 }
 
 constexpr int N = 200'000;
@@ -63,11 +63,13 @@ void performance_test() {
 		hash ^= tree.query(x);
 		t.stop();
 	}
-	if (t.time > 1000) cerr << "  too slow: " << t.time << FAIL;
-	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
 int main() {
-	stress_test();
+	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
new file mode 100644
index 0000000..0d4e10d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,79 @@
+#include "../util.h"
+struct MCH {
+	#include <datastructures/monotonicConvexHull.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);
+		auto ms = Random::distinct<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		sort(all(xs));
+		int i = 0;
+
+		vector<Line> naive;
+
+		MCH mch;
+		for (ll m : ms) {
+			ll c = Random::integer<ll>(-1000, 1000);
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = i + 100; i < j; i++) {
+				ll x = xs[i];
+
+				ll got = mch.query(x);
+				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++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+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<>{});
+	auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+	MCH 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);
+		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();
+}