Find the most vertical line in a point set in $O(n \log n)$ time

Question

Input: a set of $n$ points in general position in $\mathbb{R}^2$.

Output: the pair of points whose slope has the largest magnitude.

Time constraint: $O(n \log n)$ or better.

Please don't spoil the answer for me - I'm just stuck and looking for a nudge in the right direction. Thanks!

Answer 1

Hint:

Consider points $A$, $B$, $C$ such that $A_x < B_x < C_x$, then the slope of $AC$ is smaller or equal than the maximum of magnitudes of slopes of $AB$ and $BC$.

Good luck!

Answer 2

Hint:

Try recursion. Split the points into two halves, find the slopes for each half, then you just need to figure out the max slope defined by two separated point sets.