dunkelheit reference

dkh.datastructure.convexhull

  • CHQueryType

    Declaration

    enum CHQueryType: int;

    Convex Hull's query type

    • incr

      Declaration

      incr

    • decr

      Declaration

      decr

  • ConvexHull

    Declaration

    struct ConvexHull(T, CHQueryType queryType);

    Convex Hull Trick

    Parameters

    T

    value type

    queryType

    if queries are increase, use CHMode.incr. if queries are decrease, use CHMode.decr.

    Examples

    1. 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

    • L

      Declaration

      alias L = T[2];

      Line type y = L[0] * x + L[1]

    • insertLine

      Declaration

      void insertLine(L line);

      Insert line

      Discussion

      line's degree must be minimum or maximum

    • maxY

      Declaration

      long maxY(T x);

      get maximum y