Самый длинный путь по кварталам
Условие
В городе сетка улиц как в тетрадке: идти можно только вдоль осей X и Y, поэтому путь между двумя точками равен манхэттенскому расстоянию: |x1−x2|+|y1−y2|.
Ты отмечаешь на карте несколько мест, куда нужно успеть за день. Хочется заранее понять, какой самый длинный переход по кварталам может получиться между какими-то двумя отмеченными точками.
Найди максимальное манхэттенское расстояние среди всех пар точек.
Важно: в олимпиадных языках может понадобиться 64-битный тип (int64), потому что координаты и промежуточные значения считаются как целые числа.
Формат ввода
В первой строке дано целое число n — количество точек. Далее в n строках заданы пары целых чисел xi yi — координаты точек.
Формат вывода
Выведи одно целое число — максимальное значение |xi-xj| + |yi-yj| по всем парам различных точек.
Ограничения
2 ≤ n ≤ 2000-100000 ≤ xi, yi ≤ 100000
Пример
Ввод:
3
0 0
2 1
1 2Вывод:
3Пояснение: самое большое расстояние получается между (0,0) и (2,1) или между (0,0) и (1,2).
Как решать — идея подхода
Приём: Поворот координат (x+y и x−y)
Ключевое наблюдение: модуль в |x1-x2| + |y1-y2| мешает напрямую, но его можно «раскрыть» через два выражения. Для любых двух точек верно: |dx|+|dy| = max( (dx+dy), (dx-dy), (-dx+dy), (-dx-dy) ). Если сгруппировать по точкам, это превращается в разность значений функций x+y и x-y у двух точек. Поэтому максимум по всем парам равен: max( max(x+y)-min(x+y), max(x-y)-min(x-y) ).
Почему это работает: любое из 4 сочетаний знаков можно переписать как разность либо (x+y), либо (x-y) (просто меняются местами точки), значит самая большая манхэттенская дистанция обязательно проявится как самый большой «размах» одной из этих двух величин.
План решения:
- Пройти по всем точкам.
- Для каждой посчитать
s = x + yиd = x - y. - Поддерживать
min_s, max_s, min_d, max_d. - Ответ:
max(max_s - min_s, max_d - min_d).
Сложность: O(n) по времени и O(1) по памяти.
Частая ошибка: пытаться перебирать все пары (это O(n^2) и медленнее), или хранить суммы/разности в 32-битном типе в других языках — берите 64-битный (в Python int безопасен).
Разберись руками
Есть 3 точки на карте: (0,0), (2,1), (1,2). Ходить можно только вдоль улиц по клеткам, поэтому расстояние — это сколько шагов по X плюс сколько шагов по Y. Нужно понять, какой самый длинный переход между какими-то двумя точками.
- Отметь на сетке 3×3 три точки из ввода. Договоримся: col = x (0..2), row = y (0..2). Какие клетки нужно отметить?
- Посчитай манхэттенские расстояния для всех пар точек и возьми самое большое. (Пары всего 3.) Какое максимальное расстояние получилось?
- Теперь сделаем хитрее. Для каждой точки посчитай «сумму координат»: (0+0), (2+1), (1+2). Найди самый большой и самый маленький результат и вычти: большой − маленький. Чему равно это число?
- А теперь для каждой точки посчитай «разность координат»: (0−0), (2−1), (1−2). Снова возьми максимум и минимум и вычти: большой − маленький. Чему равно это число?
Идея: Чтобы найти самый длинный переход по кварталам, не обязательно сравнивать все пары. Можно для каждой точки посчитать два «диагональных» числа: сумму координат и разность координат. Потом для каждого списка посмотреть разброс (от минимального до максимального), и нужная длина совпадает с большим из этих двух разбросов.
Решить задачу с автопроверкой на Python →
Куда дальше
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
- С нуля до олимпиады: маршрут — сколько занимает язык, какие приёмы нужны и к какому этапу это ведёт
- Python на олимпиадах — где языка хватает с запасом, а где начинают значить лимиты — с замерами