Rubber Band Around the Nails

Hammer nails into a board at the points in points and stretch a rubber band around all of them. When you let go, it snaps into the convex hull: the smallest convex shape that contains every nail. The band bends only at some of the nails, the corners of the hull.

Write convex_hull(points) that returns the corners of the hull as a list of (x, y) tuples:

• in counter-clockwise order,
• starting from the lowest point (smallest y), and when several points share the lowest y, the leftmost of them (smallest x),
• with each corner listed once.

A nail that lies on a straight stretch of the band between two corners is not a corner, so it is left out. If all the points are the same point, return a list holding that one point. If all the points lie on one straight line, return its two end points, starting with the lowest (then leftmost) one.

Examples

convex_hull([(0, 0), (4, 0), (4, 4), (0, 4), (2, 2), (1, 3)])
# returns [(0, 0), (4, 0), (4, 4), (0, 4)]
convex_hull([(1, 1), (3, 0), (5, 1), (3, 4), (3, 2), (5, 1)])
# returns [(3, 0), (5, 1), (3, 4), (1, 1)]
convex_hull([(0, 0), (2, 0), (4, 0), (4, 2), (0, 2)])
# returns [(0, 0), (4, 0), (4, 2), (0, 2)]
convex_hull([(2, 2), (0, 0), (1, 1)])
# returns [(0, 0), (2, 2)]

In the third example, (2, 0) sits on the bottom side between two corners, so it is not a corner. In the second, (5, 1) appears twice but is listed once.

Constraints

• 1 to 50,000 points; the same point may appear more than once.
• Coordinates are integers between -109 and 109.