ConvexHull

Convex Hull Trick

struct ConvexHull (

T

CHQueryType queryType

) {

import std.algorithm : max;;

alias L = T[2];

Deque!L lines;

void insertLine(L line);

long maxY(T x);

}

Members

Aliases

L alias L = T[2]: Undocumented in source.

Functions

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

Variables

lines Deque!L lines;: Undocumented in source.

Parameters

T: value type
queryType: if queries are increase, use CHMode.incr. if queries are decrease, use CHMode.decr.

Examples

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

Meta

Source

See Implementation

dkh datastructure convexhull enums

CHQueryType

structs

ConvexHull