mzuenni tests

1 files changed, 26 insertions, 0 deletions

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
new file mode 100644
index 0000000..e7b9b3e
--- /dev/null
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,26 @@
+struct Envelope {
+	struct Line {
+		ll m, b;
+		ll operator()(ll x) { return m*x+b; }
+	};
+
+	vector<Line> ls;
+	int ptr = 0;
+
+	static 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);
+	}
+
+	void add(ll m, ll b) {
+		while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) {
+			ls.pop_back();
+		}
+		ls.push_back({m, b});
+		ptr = min(ptr, sz(ls) - 1);
+	}
+
+	ll query(ll x) {
+		while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+		return ls[ptr](x);
+	}
+};