Ближайшая пара точек

Даны $n$ точек на плоскости. Найти наименьшее расстояние между какими-либо двумя.

Перебор всех пар — $O(n^2)$, при $n = 10^5$ не проходит. Классическое решение через разделяй и властвуй даёт $O(n \log n)$, но пишется долго. Сканирующая прямая даёт то же самое и заметно короче.

Идея

Отсортируем точки по $x$ и будем идти слева направо, поддерживая текущий лучший ответ $d$.

Когда обрабатываем точку $p$, кандидатами на пару могут быть только точки, у которых:

• $x$ отличается меньше чем на $d$ — иначе расстояние заведомо больше;
• $y$ отличается меньше чем на $d$ — по той же причине.

Первое условие обеспечивается окном по $x$: точки, ушедшие далеко влево, выбрасываются. Второе — тем, что окно хранится отсортированным по $y$, и нужный диапазон находится двумя бинарными поисками.

sort(p.begin(), p.end());              // по x, затем по y
set<pair<long long, long long>> window;   // (y, x)
double best = 1e18;
size_t left = 0;

for (size_t i = 0; i < p.size(); i++) {
    while (left < i && p[i].first - p[left].first >= best) {
        window.erase({p[left].second, p[left].first});
        left++;
    }
    long long d = (long long)ceil(best);
    auto lo = window.lower_bound({p[i].second - d, LLONG_MIN});
    auto hi = window.upper_bound({p[i].second + d, LLONG_MAX});
    for (auto it = lo; it != hi; ++it) {
        double dx = p[i].first - it->second, dy = p[i].second - it->first;
        best = min(best, sqrt(dx * dx + dy * dy));
    }
    window.insert({p[i].second, p[i].first});
}

Проверено: на двадцати тысячах случайных наборов до четырнадцати точек ответ совпал с перебором всех пар с точностью до $10^{-9}$.

Почему это быстро

Кажется, что внутренний цикл может перебрать много точек. На деле — не больше константы.

Все точки окна лежат в полосе шириной $d$ по $x$ и, для текущей точки, в полосе высотой $2d$ по $y$. Получается прямоугольник $d \times 2d$. При этом любые две точки окна находятся на расстоянии не меньше $d$ друг от друга — иначе $d$ давно бы обновился.

В прямоугольник $d \times 2d$ нельзя уложить больше примерно восьми точек с попарными расстояниями не меньше $d$. Значит, внутренний цикл делает $O(1)$ итераций.

Итог: $O(n \log n)$, где логарифм — от сортировки и операций с множеством.

Детали, на которых спотыкаются

Множество хранит пары $(y, x)$, а не $(x, y)$. Порядок именно по $y$, иначе бинарный поиск ищет не то. Второй компонент нужен, чтобы совпадающие $y$ не схлопывались.

Окно двигается указателем left, а не пересчитывается. Это два указателя: оба индекса идут только вправо, суммарно $O(n)$ удалений.

Границы поиска по $y$ округляются вверх. Иначе из-за вещественного best можно пропустить точку, лежащую ровно на границе.

Совпадающие точки дают ответ ноль. Проверьте, что код это выдерживает: расстояние ноль корректно, но best = 0 схлопнет окно, и дальше сравнение >= best начнёт вести себя иначе. Обычно проще отдельно проверить наличие дубликатов и сразу вернуть ноль.

Работа в целых числах

Сравнивать расстояния можно по квадратам, не извлекая корень. Тогда весь алгоритм остаётся в целых числах и не теряет точности.

Единственная тонкость — граница окна: сравнивать нужно квадрат разности по $x$ с текущим квадратом ответа, а для поиска по $y$ брать целочисленный корень с округлением вверх.

Если задача просит само расстояние, корень берётся один раз в конце.

Родственные задачи

Ближайшая пара среди точек двух цветов. Тот же алгоритм, но в окно кладём только точки одного цвета, а ищем — для точек другого.

Есть ли пара ближе, чем $d$. Проще: фиксированное окно, никакого обновления best, и можно выйти при первой находке.

Наибольшее расстояние (диаметр множества). Задача другая: ответ достигается на вершинах выпуклой оболочки, и решается методом вращающихся калиперов. Сканирующая прямая тут не помогает.