Convex-hull of points on a general second-order parabola (Ex-Googler)

You are given N>=3 numbers x[1..N] and coefficients a,b,c.
Calculate planar points of the form (x, ax^2 + bx + c) and then find their convex hull.
Return the coordinates of the points in counter clock-wise order.

Hint 1:
On which side of an edge do all of the vertices of the convex hull lie?

Hint 2:
Consider just the parabola itself as a continuous function : if you draw a tangent at any point on the point of a parabola, on which side of the tangent line do all of the points on the parabola lie?

Hint 3:
How can you combine hints 1 and 2? Is there any difference between the continuous and the discrete case?

Hint 4:
Which problem can be reduced to finding convex hulls?

Example:
input: [ [3, -1, 1], [a=1, b=1, c=1] ]
output: [ [-1, 1], [1, 3], [3, 13] ]

Comments (2)