From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 17 Aug 2024 20:30:08 +0200
Subject: improved monotonic onvex hull

---
 content/datastructures/monotonicConvexHull.cpp |   4 +--
 tcr.pdf                                        | Bin 691092 -> 691111 bytes
 test/datastructures/monotonicConvexHull.cpp    |  41 ++++++++++++++++++++-----
 3 files changed, 35 insertions(+), 10 deletions(-)

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index e84ad86..f1721ae 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,5 +1,5 @@
 // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
-// Gerade hat kleinere Steigung als alle vorherigen.
+// Gerade hat kleineres pair(m, c) als alle vorherigen.
 struct Line {
 	ll m, c;
 	ll operator()(ll x) {return m*x+c;}
@@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 }
 
-ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert
+ll query(ll x) { // x >= letztes x, 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);
diff --git a/tcr.pdf b/tcr.pdf
index d107dab..199c3de 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 9edfb4b..0415068 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -13,17 +13,30 @@ 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);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
-		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		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<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
+
+		auto xs = Random::integers<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>(-range, range);
+		for (int k = 0; k < n; k++) {
+			ll m = ms[k];
+			ll c = cs[k];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
@@ -46,18 +59,30 @@ void stress_test_independent(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);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
+		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<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
 
 		vector<Line> naive;
 
 		MCH mch;
-		for (ll m : ms) {
-			ll c = Random::integer<ll>(-range, range);
+		for (int i = 0; i < n; i++) {
+			ll m = ms[i];
+			ll c = cs[i];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
-			auto xs = Random::distinct<ll>(100, -range, range);
+			auto xs = Random::integers<ll>(100, -range, range);
 			sort(all(xs));
 			auto tmp = mch;
 
-- 
cgit v1.2.3