datastructures/test/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
26
27

#define sz(X) ((int)size(X))
#include "../monotonicConvexHull.cpp"

int main() {
	{
		Envelope env;
		env.add(10, 0);
		assert(env.query(0) == 0);
		assert(env.query(1) == 10);
		env.add(8, 5);
		assert(env.query(1) == 10);
		assert(env.query(2) == 20);
		assert(env.query(3) == 29);
		env.add(7, 10);
		assert(env.query(10) == 80);
		env.add(0, 0);
		assert(env.query(11) == 0);
	}

	{
		Envelope env;
		env.add(1, 0);
		env.add(0, 10);
		env.add(-1, 10);
		assert(env.query(7) == 3);
	}
}