[Algorytmy] Szukanie prostej na OY

[skytrack]

Witam, otóż mam pewien problem, zadanie polega na zbudowaniu najkrótszej ścieżki łączącej wszystkie punkty w układzie współrzędnych jednak przy ustalonych warunkach.
Link do zdjęcia:
Na tym zdjeciu widac jak to mniej wiecej ma byc ulozone, musi być jedna prosta od skrajnie lewego \(\displaystyle{ x}\) do skrajnie prawego \(\displaystyle{ x}\) i teraz pytanie o to jak wybrac odpowiednia prosta \(\displaystyle{ y}\) by połączone punkty tworzyły jak najmniejsza długość. Raczej nieoptymalnym rozwiazaniem bylo by iterowanie po kazdym \(\displaystyle{ y}\). Czy istnieje jakis sposób na szybkie znalezienie takiej prostej?

[Afish]

Posortuj domki po współrzędnej \(\displaystyle{ y}\), oznacz te wartości jako \(\displaystyle{ y_1, \ldots, y_n}\), następnie przyjmij, że Twoja prosta przecina oś \(\displaystyle{ OY}\) w punkcie \(\displaystyle{ (0;Y)}\) (czyli prosta jest "na wysokości" \(\displaystyle{ Y}\)). Teraz załóż, że \(\displaystyle{ Y}\) znajduje się między domkiem \(\displaystyle{ i}\) a \(\displaystyle{ i+1}\) i wyznacz wzór na sumę odległości dróg.
Zastanów się teraz, jak ta suma będzie się zmieniała, gdy prosta będzie się zbliżała do domku \(\displaystyle{ i}\) lub do domku \(\displaystyle{ i+1}\). A potem użyj zamiatania, aby znaleźć najlepsze \(\displaystyle{ i}\).
Rozważ także sytuację, gdy kilka domków ma jednakową współrzędną \(\displaystyle{ x}\).