Problem polega na znalezieniu zestawu wszystkich punktów całkowitych, które dają minimalną sumę na wszystkie odległości na Manhattanie od danego zestawu punktów!

Na przykład:

pozwala mieć określony zestaw punktów {P1, P2, P3 ... Pn}

Podstawowym problemem jest znalezienie punktu o nazwie X, który miałby minimalną sumę we wszystkich odległościach od punktów {P1, P2, P3 ... Pn}.

tj. | P1-X | + | P2-X | + .... + | Pn-X | = D, gdzie D będzie minimalne na wszystkich X.

Idąc o krok dalej, może być więcej niż jedna wartość X spełniająca powyższy warunek. tj. więcej niż jeden X może być możliwy, co dałoby tę samą wartość D. Więc musimy znaleźć wszystkie takie X.

Jednym z podstawowych podejść, o którym każdy może myśleć, będzie znalezienie mediany wejść, a następnie brutalne wymuszenie współrzędnych wymienionych wten post

Ale problem z takim podejściem jest taki, że jeśli mediana daje dwie wartości, które są bardzo od siebie oddalone, to kończymy brutalnie wymuszając wszystkie punkty, które nigdy nie będą działać w danym czasie.

Czy jest więc jakieś inne podejście, które dałoby wynik, nawet jeśli punkty są bardzo daleko od siebie (gdzie mediana daje zakres rzędu 10 ^ 9).