Блог пользователя _dangerous_

Баянистая задача
Автор _dangerous_, 11 лет назад, По-русски

Задача довольно известная, но я не знаю как быстро ее решать: дано N точек (с целочисленными координатами), нужной найти такую точку, максимальное манхэттенское расстояние (|x1-x2|+|y1-y2|) до которой минимально. как максимально быстро можно решать эту задачу?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Повернуть координаты на 45 градусов. Тогда расстояние будет не суммой разностей координат, а максимумом разностей.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    повернуть относительно начала координат?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Относительно любой точки.

      Важно не это, а то, что в терминах минимальной и максимальной координаты, разделив задачу на две независимые подзадачи, решать некоторые задачи существенно проще.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        либо я что-то не понял, но вот например есть точка (0;3), поворачиваем ее относительно начала координат (-3*sqrt(2)/2; 3*sqrt(2)/2), максимум расстояние не будет равен 3м, что я не так понял?

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Откуда корни? В посте написано про манхэттенское расстояние.

          Повернув метрику ρ1 на 45 градусов, мы получаем ρ∞, и наоборот. Например:

          (u, v) = (x + y, x - y)

          Обратно:

          Можно ещё прочитать вот это и наглядно увидеть, как выглядит круг при p = 1 и p = ∞.

          → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А такое не зайдёт? Делаем бинарный поиск по ответу, чтобы проверить, можно ли получить такое расстояние, описываем вокруг каждой точке квадрат, соответствующего радиуса. Далее пересекаем все квадраты, это будет за линиию, так как пересечение прямоугольников — опять прямоугольник. Если пересечение пусто, то увеличиваем ответ, иначе уменьшаем. В итоге получим множество точек с минимальным макс расстоянием. По идее это будет отрезок или точка.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Только пересекаться будут ромбы(вида diffL <= x — y <= diffR, sumL <= x + y <= sumR).

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    да это понятно, я просто думал, может что-то неочевидное и более быстрое.

    → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

O(N)
Найдем восемь точек — по две ближайшие к (+inf,+inf),(-inf,+inf),(+inf,-inf),(-inf,-inf). Максимальное расстояние от точки до любой другой будет равно максимальному расстоянию до одной из этих восьми.
Интуитивно кажется верным.
Задача Метро с российских сборов (не знаю, каких), вероятно, может дать много подсказок на счет этой.
UPD: Хмм, похоже, достаточно по одной точке в каждой направлении в этой задаче. Нестрого почему это правильно — потому, что мы имеем четыре случая (x'<x, x'>=x), а также (y'<y, y'>=y), каждая из четырех выбранных точек максимизириует какой-то из случаев (зависит от знака). При желании можно написать перебор и сверить, и брут и это решение выглядят очень просто.

→ Ответить