Нахождение максимального расстояния между координатами (x, y)

Осталось рассмотреть только два случая, если мы будем рассматривать только такие результаты, что Xi <= Xj.

• Если Yi <= Yj, то расстояние (Xj + Yj) - (Xi + Yi)
• В противном случае расстояние (Xj - Yj) - (Xi - Yi)

Разбив его на эти случаи, я избавился от функции абсолютного значения, что значительно упростило рассуждение о расстояниях.

Итак, мы просто выбираем точки с минимумом и максимумом x+y и вычисляем расстояние. Затем выберите точки с минимумом и максимумом x-y и вычислите расстояние. Одно из этих двух расстояний - ваш максимум.

Это можно сделать в O(n), что является асимптотически оптимальным.

Это довольно просто и может быть рассчитано за O(n)

Пусть x1>x2 и y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2)

Пусть x1>x2 и y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2)

Теперь замените x1 на x2, и вы получите тот же результат.

Итак, в целом ваше решение

max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) ) 

Лучшее, что можно сделать с такими вопросами, - это попытаться получить небольшие результаты, которые помогут вам решить общую проблему.

Например, нетрудно определить, что для любых трех точек, A, B и C, которые имеют условие, что B находится между (подробнее об этом через секунду) A и C, B никогда не будет дальше от четвертой точки D, чем одна из точек A и C. При стандартной евклидовой метрике расстояния точка находится между двумя другими точками, если она лежит на соединяющем их отрезке. Для манхэттенских измерений это не так просто - отчасти потому, что концепция сегмента не так хорошо понятна.

Более общий способ описания «между» состоит в следующем (с использованием обозначения, что расстояние от A до B равно | AB |): точка B находится между двумя точками A, C, если | AB | + | BC | = | AC |

Вы можете видеть, что на евклидовом расстоянии это означает, что B лежит на отрезке, соединяющем A и C.

На манхэттенском расстоянии это означает, что точка B содержится в прямоугольнике, определяемом A и C (который, конечно, может быть прямым сегментом, если AC параллелен одной из осей).

Этот результат означает, что для любой точки, если она находится между двумя существующими точками, она не может быть дальше от любых новых точек, добавленных к набору, чем две, которые ее окружают.

Эта информация не решает проблему для вас, но позволяет отказаться от многих возможных будущих расчетов. Как только вы определили, что точка находится между двумя другими, отслеживать ее нет смысла.

Таким образом, вы можете решить эту проблему, отслеживая только самые удаленные точки и не обращая внимания на те, которые попадают внутрь.

Интересное упражнение для случайного наблюдателя

Докажите, что у вас может быть не более 4 различных точек, так что ни одна из точек не находится между двумя другими в манхэттенском смысле.

С этим вторым результатом становится ясно, что вам нужно будет отслеживать только до 4 точек.

Некоторые из других уже представленных методов, вероятно, быстрее, но это веселее!

Дополнительный кредит

Обобщите эти идеи до n измерений.

первым большим улучшением будет:

for ( X: 0 -> n )
    for ( Y: X -> n )
        { compute the distance between X and Y }

так как расстояние между X и Y такое же, как расстояние между Y и X. Это сократит ваши вычисления вдвое ...

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