Ближайшая Пара ТочекClosest Pair of Points

Точки сортируются по x-координате (один раз, O(n log n)), затем делятся вертикальной линией на левую и правую половины по n/2 точек. Рекурсивно находится минимальное расстояние d_L в левой половине и d_R в правой; d = min(d_L, d_R) — кандидат на итоговый ответ. Но это ещё не всё: ближайшая пара может состоять из одной точки слева и одной справа, рядом с самой разделяющей линией. Наивная проверка всех таких кросс-пар — снова O(n²). Ключевое наблюдение: если такая более близкая пара существует, обе её точки обязаны лежать в вертикальной полосе шириной 2d вокруг разделяющей линии (иначе расстояние по x одной уже превышает d, и пара не может быть ближе d).Points are sorted by x-coordinate (once, O(n log n)), then split by a vertical line into left and right halves of n/2 points each. The minimum distance d_L in the left half and d_R in the right half are found recursively; d = min(d_L, d_R) is the candidate final answer. But that's not the whole story: the closest pair might consist of one point from the left and one from the right, near the dividing line itself. Naively checking all such cross-pairs is again O(n²). The key observation: if such a closer pair exists, both its points must lie within a vertical strip of width 2d around the dividing line (otherwise one point's x-distance alone already exceeds d, and the pair can't be closer than d).

Внутри полосы всё ещё может быть до n точек, и наивная проверка всех пар внутри неё — снова O(n²), что убило бы весь выигрыш. Спасает второе наблюдение: если точки в полосе отсортировать по y-координате, то для каждой точки достаточно сравнить её только с ближайшими 7 (по некоторым источникам — 6) соседями в этом y-порядке, а не со всеми. Доказательство — геометрическая упаковка: разобьём полосу на воображаемые квадраты d/2 × d/2. В каждом таком квадрате не может находиться больше одной точки из уже найденного набора с попарным расстоянием ≥ d (иначе две точки в квадрате со стороной d/2 были бы на расстоянии < d, противоречие). Любые две точки, чьи y-координаты отличаются меньше чем на d, попадают в полосу высотой d, которая покрывается не более чем 8 такими квадратами (2 по ширине полосы 2d, 4 по высоте d) — значит, для любой точки в полосе среди следующих по y-порядку точек, отстоящих не более чем на d, может быть не больше 7 кандидатов (сама точка занимает один из 8 квадратов). Отсюда: для каждой из n точек в полосе — не более 7 сравнений, весь merge-шаг — O(n). Итоговое T(n) = 2T(n/2) + O(n) (сортировка по x делается один раз до рекурсии, сортировка полосы по y — через слияние отсортированных списков, тоже O(n) на уровень) даёт по Master theorem (2.1.2) O(n log n).There can still be up to n points inside the strip, and naively checking all pairs within it is again O(n²), which would kill the entire payoff. A second observation saves it: if the strip's points are sorted by y-coordinate, then for each point it's enough to compare it against only the nearest 7 (some sources say 6) neighbors in that y-order, not all of them. The proof is a geometric packing argument: divide the strip into imaginary d/2 × d/2 squares. No such square can contain more than one point from the already-found set with pairwise distance ≥ d (otherwise two points in a square of side d/2 would be less than d apart, a contradiction). Any two points whose y-coordinates differ by less than d fall within a strip of height d, which is covered by at most 8 such squares (2 across the strip's width of 2d, 4 down its height d) — so for any point in the strip, among the points that follow it in y-order and are no more than d away, there can be at most 7 candidates (the point itself occupies one of the 8 squares). Hence: for each of the n points in the strip, at most 7 comparisons — the whole merge step is O(n). The resulting T(n) = 2T(n/2) + O(n) (the x-sort happens once before the recursion; sorting the strip by y is done via merging already-sorted lists, also O(n) per level) gives O(n log n) by the Master theorem (2.1.2).

double closestPair(std::vector<Point>& pts_by_x) {   // pts_by_x уже отсортирован по x// pts_by_x already sorted by x
    int n = pts_by_x.size();
    if (n <= 3) return bruteForce(pts_by_x);

    int mid = n / 2;
    Point midPoint = pts_by_x[mid];
    double dl = closestPair({pts_by_x.begin(), pts_by_x.begin()+mid});
    double dr = closestPair({pts_by_x.begin()+mid, pts_by_x.end()});
    double d = std::min(dl, dr);

    std::vector<Point> strip;                            // точки внутри полосы шириной 2d// points inside the width-2d strip
    for (auto& p : pts_by_x)
        if (std::abs(p.x - midPoint.x) < d) strip.push_back(p);
    std::sort(strip.begin(), strip.end(), byY);           // сортировка полосы по y// sort the strip by y

    for (size_t i = 0; i < strip.size(); i++)
        for (size_t j = i+1; j < strip.size() && (strip[j].y - strip[i].y) < d; j++)
            d = std::min(d, dist(strip[i], strip[j]));    // не более 7 итераций j на каждый i// at most 7 iterations of j per i

    return d;
}

Точки на плоскости — демонстрация проигрывает разбиение вертикальной линией на две половины, рекурсивное нахождение минимума в каждой, а затем выделяет полосу шириной 2d и подсвечивает сравнения внутри неё, ограниченные соседями по y.Points in the plane — the demo auto-plays the vertical split into two halves, recursively finding the minimum in each, then highlights the width-2d strip and the comparisons inside it, bounded to y-neighbors.