ConvexHull

Convex Hull Trick

struct ConvexHull (

CHQueryType queryType

) {

Deque!L lines;

void insertLine(L line);

long maxY(T x);

}

Members

Functions

insertLine void insertLine(L line): Insert line
maxY long maxY(T x): get maximum y

Examples

1 ConvexHull!(int, CHQueryType.incr) c;
2 c.insertLine([1, 4]);
3 c.insertLine([2, 1]);
4 c.insertLine([3, -100]);
5 assert(c.maxY(-1) == 3); // 1 * (-1) + 4 = 3
6 c.insertLine([-10, 100]);
7 assert(c.maxY(2) == 80); // 2 * (-10) + 100 = 80

ConvexHull

Members

Functions

Examples

Meta

Source