Задача довольно известная, но я не знаю как быстро ее решать: дано N точек (с целочисленными координатами), нужной найти такую точку, максимальное манхэттенское расстояние (|x1-x2|+|y1-y2|) до которой минимально. как максимально быстро можно решать эту задачу?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
25:10:52
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
25:10:52
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 16:24:09 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Повернуть координаты на 45 градусов. Тогда расстояние будет не суммой разностей координат, а максимумом разностей.
повернуть относительно начала координат?
Относительно любой точки.
Важно не это, а то, что в терминах минимальной и максимальной координаты, разделив задачу на две независимые подзадачи, решать некоторые задачи существенно проще.
либо я что-то не понял, но вот например есть точка (0;3), поворачиваем ее относительно начала координат (-3*sqrt(2)/2; 3*sqrt(2)/2), максимум расстояние не будет равен 3м, что я не так понял?
Откуда корни? В посте написано про манхэттенское расстояние.
Повернув метрику ρ1 на 45 градусов, мы получаем ρ∞, и наоборот. Например:
Обратно:
Можно ещё прочитать вот это и наглядно увидеть, как выглядит круг при p = 1 и p = ∞.
спасибо, классная статья.
А такое не зайдёт? Делаем бинарный поиск по ответу, чтобы проверить, можно ли получить такое расстояние, описываем вокруг каждой точке квадрат, соответствующего радиуса. Далее пересекаем все квадраты, это будет за линиию, так как пересечение прямоугольников — опять прямоугольник. Если пересечение пусто, то увеличиваем ответ, иначе уменьшаем. В итоге получим множество точек с минимальным макс расстоянием. По идее это будет отрезок или точка.
Только пересекаться будут ромбы(вида diffL <= x — y <= diffR, sumL <= x + y <= sumR).
А, точно) Ну всегда можно повернуть
да это понятно, я просто думал, может что-то неочевидное и более быстрое.
O(N)
Найдем восемь точек — по две ближайшие к (+inf,+inf),(-inf,+inf),(+inf,-inf),(-inf,-inf). Максимальное расстояние от точки до любой другой будет равно максимальному расстоянию до одной из этих восьми.
Интуитивно кажется верным.
Задача Метро с российских сборов (не знаю, каких), вероятно, может дать много подсказок на счет этой.
UPD: Хмм, похоже, достаточно по одной точке в каждой направлении в этой задаче. Нестрого почему это правильно — потому, что мы имеем четыре случая (x'<x, x'>=x), а также (y'<y, y'>=y), каждая из четырех выбранных точек максимизириует какой-то из случаев (зависит от знака). При желании можно написать перебор и сверить, и брут и это решение выглядят очень просто.