Проблема здесь состоит в том, чтобы найти множество всех целочисленных точек, которые дают минимальную сумму на всех расстояниях Манхэттена от данного набора точек!

Например:

давайте иметь заданный набор точек {P1, P2, P3 ... Pn}

Основная проблема состоит в том, чтобы найти точку, скажем, X, которая имела бы минимальную сумму на всех расстояниях от точек {P1, P2, P3 ... Pn}.

т.е. | P1-X | + | P2-X | + .... + | Pn-X | = D, где D будет минимальным по всем X.

Если продвинуться дальше, может быть более одного значения X, удовлетворяющего указанному выше условию. то есть возможно более одного X, что давало бы одно и то же значение D. Итак, нам нужно найти все такие X.

Один из основных подходов, который каждый может придумать, состоит в том, чтобы найти медиану входных данных, а затем перебрать координаты, которые упоминаются вэта почта

Но проблема такого подхода заключается в том, что если медиана дает два значения, которые очень сильно отличаются друг от друга, то мы в конечном итоге перебиваем все точки, которые никогда не пройдут в данный момент времени.

Итак, есть ли другой подход, который дал бы результат, даже когда точки очень далеко друг от друга (где медиана дает диапазон, который составляет порядка 10 ^ 9).