Convex Hull Trick Envelope

Problem

Query the lower envelope of a set of lines.

Given lines as [slope, intercept] pairs and a query x, return [value, index] for the line minimizing slope * x + intercept. The lowest index wins ties.

Hint

The envelope is the pointwise minimum over all inserted lines.

Test cases

case 1

in: [[[-1,0],[1,-4]],1]

expected: [-3,1]

case 2

in: [[[2,0],[1,1],[0,5]],3]

expected: [4,1]

case 3

in: [[[0,3],[0,3]],2]

expected: [3,0]

Starter codePython

def convex_hull_envelope(lines, x):
    # Returns [value, index]
    # Your code here
    pass

3 test cases · run your code against them in the editor