When I first read this problem, I think this is very similar to the problem of finding the convex hull of a set of points. The optimal solution to do this is O(nlogn). I haven't code it up yet, but from reading what's on the discussion, it seems that O(nlogn) is the best run time. It might be an overkill to think this way.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.