The fence around the stations

Stations stand at whole-number points. A straight-sided fence must enclose them all and be as short as possible: it is the convex hull. Return its corners counterclockwise, starting from the point with the smallest y (the smallest x among those, if several). Points that lie on an edge between two corners are not corners. Repeated points count once.

hull([(0, 0), (2, 0), (2, 2), (0, 2), (1, 1)])
# [(0, 0), (2, 0), (2, 2), (0, 2)]
hull([(0, 0), (1, 0), (2, 0), (2, 2), (0, 2)])
# [(0, 0), (2, 0), (2, 2), (0, 2)]
hull([(2, 2), (0, 0), (5, 5)])   # [(0, 0), (5, 5)]

If all the points lie on one line, return its two ends (the lower one first); if there is only one point, return it alone.

Limits

• Up to 200,000 points, with coordinates up to 10⁹. The big tests have 5 seconds each.
• On one test every point is a corner, so gift wrapping (O(n · h)) is too slow.