Encontrar la línea más vertical en un conjunto de puntos en $O(n \log n)$ tiempo

Question

Entrada: un conjunto de $n$ puntos en posición general en $\mathbb{R}^2$ .

Salida: el par de puntos cuya pendiente tiene la mayor magnitud.

Limitación de tiempo: $O(n \log n)$ o mejor.

Por favor, no me estropees la respuesta, sólo estoy atascado y busco un empujón en la dirección correcta. Gracias.

Answer 1

Una pista:

Considere los puntos $A$ , $B$ , $C$ tal que $A_x < B_x < C_x$ entonces la pendiente de $AC$ es menor o igual que el máximo de las magnitudes de las pendientes de $AB$ y $BC$ .

Buena suerte.

Answer 2

Una pista:

Prueba la recursión. Divide los puntos en dos mitades, encuentra las pendientes de cada mitad y luego sólo tienes que calcular la pendiente máxima definida por dos conjuntos de puntos separados.