Yes there is a much more efficient way to do this. Off the cuff I can write an O(N log(N)) algorithm. As this is a test question, the point is not solving it it is the process of solving.
The problem you seem to have is a perspective issue. Try reducing the size of the problem down.
- How would you solve this for two points?
- How would you solve this for three points? four points? five points?
- Given that you've already solved this problem for K points, can you solve it for K+1 points?
- Does that K+1 point need to have certain properties?
- Would receiving the points in a particular order make it easier to solve?
- Would considering the points one, two, three at a time make it easier to solve?
- How does each line behave as a point is added?
- Can you take advantage of that behaviour?
At this point you'll probably have worked out if and how to sort the points, how they are picked, and how many points you'll consider at once. You will know how to update the solution for the next point, and you'll know that your answer is correct after having considered all points.