Ho problemi con una domanda di codifica che ho trovato utile per un'intervista:
Un grafico a dispersione di punti su una pagina, disegna due linee orizzontali (queste linee sono parallele) attraverso la pagina in modo tale che la distanza perpendicolare y di una linea da tutti i punti sia minimizzata. Conta la distanza totale da ciascun punto alla linea più vicina (conta solo la distanza da ciascun punto alla linea più vicina, ignora la distanza più lunga, quando la distanza è la stessa, scegli uno dei due). Descrivi un algoritmo per trovare queste due linee.
Il mio approccio:
Ho preso in considerazione la forzatura bruta di questo controllando tutte le possibilità in intervalli di 1 a partire dall'asse y più alto che termina con l'asse y più basso dei punti, ma forse non è il modo migliore. Ho anche considerato di dividere i punti in due gruppi in base all'asse y, tuttavia ci sono alcuni casi limite che falliranno.
Qualcuno sa un modo più efficiente per farlo?