Вопрос по algorithm – Все точки с минимальным Манхэттенским расстоянием от всех других заданных точек [Оптимизировано]
Проблема здесь состоит в том, чтобы найти множество всех целочисленных точек, которые дают минимальную сумму на всех расстояниях Манхэттена от данного набора точек!
Например:
давайте иметь заданный набор точек {P1, P2, P3 ... Pn}
Основная проблема состоит в том, чтобы найти точку, скажем, X, которая имела бы минимальную сумму на всех расстояниях от точек {P1, P2, P3 ... Pn}.
т.е. | P1-X | + | P2-X | + .... + | Pn-X | = D, где D будет минимальным по всем X.
Если продвинуться дальше, может быть более одного значения X, удовлетворяющего указанному выше условию. то есть возможно более одного X, что давало бы одно и то же значение D. Итак, нам нужно найти все такие X.
Один из основных подходов, который каждый может придумать, состоит в том, чтобы найти медиану входных данных, а затем перебрать координаты, которые упоминаются вэта почта
Но проблема такого подхода заключается в том, что если медиана дает два значения, которые очень сильно отличаются друг от друга, то мы в конечном итоге перебиваем все точки, которые никогда не пройдут в данный момент времени.
Итак, есть ли другой подход, который дал бы результат, даже когда точки очень далеко друг от друга (где медиана дает диапазон, который составляет порядка 10 ^ 9).
то каждая точка в этом интервале так же хороша, как и любая другая.
Так что в зависимости от того, что вы хотите сделать с этими точками позже, вы можете либо вернуть диапазон, либо перечислить точки в этом диапазоне. Обойти это невозможно ..
Очевидно, что в двух измерениях вы получите растущий прямоугольник, в трех измерениях ограничивающий кубоид и т. Д ..
Результат всегда будет декартовым произведением диапазонов, полученных для каждого измерения, поэтому вы можете вернуть список этих диапазонов в результате.
так как они увеличивают расстояние независимо друг от друга. Это сводит вопрос к нахождению, учитывая n точек на линии, точки с минимальной суммой расстояний до других точек. Это просто: любая точка между двумя медианами (включительно) удовлетворит это.
Proof: Если у нас будет четное количество очков, будет два медианы. Точка между двумя медианами будет иметь n / 2 точки слева и n / 2 точки справа и общую сумму расстояний до этих точек S.
Если мы переместим его на одну точку влево, S увеличится на n / 2 (поскольку мы удаляемся от крайних правых точек) и вниз на n / 2 (поскольку мы движемся к крайним левым точкам), так что в целом S остается прежним. Это верно до тех пор, пока мы не достигнем самой левой средней точки. Когда мы двигаемся на одну левую часть от крайней левой средней точки, у нас теперь есть (n / 2 + 1) точек вправо и (n / 2 - 1) точек влево, поэтому S повышается на два. Продолжение влево только увеличит S.
По той же логике все точки справа от самой правой медианы также имеют более высокое значение S.
Если у нас нечетное количество баллов, то есть только одна медиана. Используя ту же логику, что и выше, мы можем показать, что она имеет наименьшее значение S.
я также думаю, что для нечетного числа N точек на сетке будет только одна точка (т. Е. МЕДИАНА), которая будет находиться на минимальной сумме расстояния Манхэттена от всех других точек.
Для четного значения N сценарий будет немного другим.
По мне, если два комплектаX = {1,2} and Y= {3,4}
их декартово произведение всегда будет 4.
т.е.X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}
. Это то, что я понял до сих пор.
В качестве ДАЖЕ количества значений мы всегда принимаем значения «СРЕДНЕЕ ДВА» в качестве СРЕДНЕГО. Взятие 2 из X и 2 из Y всегда вернет декартово произведение 4 баллов.
Поправь меня, если я ошибаюсь.