content/datastructures/monotonicConvexHull.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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 (ssize(ls) > 1
		  && bad(ls.end()[-2], ls.back(), {m,b})) ls.pop_back();
		ls.push_back({m, b});
		ptr = min(ptr, (int)ssize(ls) - 1);
	}

	ll query(ll x) {
		while (ptr < ssize(ls)-1 && ls[ptr+1](x) < ls[ptr](x)) ptr++;
		return ls[ptr](x);
	}
};