HA_62_Pairs

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <utility>

using namespace std;

struct Point {
    double x, y;
    int idx; // оригинальный индекс
};

// Результат: два индекса и
// квадрат минимального расстояния
struct ClosestPairResult {
    int idx1;
    int idx2;
    double dist2; // квадрат расстояния
};

class ClosestPair {
public:
    // Внешний интерфейс
    static ClosestPairResult findClosest(const vector<Point>& points) {
        int n = points.size();
        vector<Point> pts_by_x = points;
        sort(pts_by_x.begin(), pts_by_x.end(), [](const Point& a, const Point& b) {
            return a.x < b.x;
        });
        vector<Point> pts_by_y = pts_by_x; // будет переупорядочиваться в рекурсии
        return recursiveSolve(pts_by_x, pts_by_y, 0, n);
    }

private:
    // Рекурсивное решение на диапазоне [l, r)
    static ClosestPairResult recursiveSolve(vector<Point>& pts_by_x,
                                            vector<Point>& pts_by_y,
                                            int l, int r) {
        int len = r - l;
        if (len <= 1) {
            return { -1, -1, numeric_limits<double>::infinity() };
        }
        int mid = l + len / 2;
        double mid_x = pts_by_x[mid].x;

        // Разделим pts_by_y на левую и
        // правую части по x, сохраняя сортировку по y
        vector<Point> left_by_y;
        vector<Point> right_by_y;
        left_by_y.reserve(mid - l);
        right_by_y.reserve(r - mid);
        for (const Point& p : pts_by_y) {
            if (p.x < mid_x || (p.x == mid_x && p.idx == pts_by_x[mid].idx && left_by_y.size() < (size_t)(mid - l))) {
                left_by_y.push_back(p);
            } else if ((int)right_by_y.size() < (r - mid)) {
                right_by_y.push_back(p);
            } else {
                left_by_y.push_back(p);
            }
        }

        // Левый и правый рекурсивно
        ClosestPairResult left_res = recursiveSolve(pts_by_x, left_by_y, l, mid);
        ClosestPairResult right_res = recursiveSolve(pts_by_x, right_by_y, mid, r);

        // Берём лучший из левого/правого
        ClosestPairResult best = (left_res.dist2 < right_res.dist2) ? left_res : right_res;
        double delta2 = best.dist2;
        double delta = sqrt(delta2);

        // Строим полосу: точки с |x - mid_x| < delta
        vector<Point> strip;
        strip.reserve(r - l);
        for (const Point& p : pts_by_y) {
            if (fabs(p.x - mid_x) < delta) {
                strip.push_back(p);
            }
        }

        // Сканируем полосу: для каждой
        // точки проверяем следующие до 7 по y
        for (size_t i = 0; i < strip.size(); ++i) {
            // Ограничиваем количество проверок
            // — следующими по y достаточно проверять константу
            for (size_t j = i + 1; j < strip.size() && j <= i + 7; ++j) {
                double dy = strip[j].y - strip[i].y;
                if (dy * dy >= delta2) break; // дополнительная обрезка
                double dx = strip[j].x - strip[i].x;
                double d2 = dx * dx + dy * dy;
                if (d2 < delta2) {
                    delta2 = d2;
                    delta = sqrt(delta2);
                    best = { strip[i].idx, strip[j].idx, delta2 };
                }
            }
        }

        return best;
    }
};

int main() {
    vector<Point> pts = {
            {0,1,0}, {0,4,1}, {2,1,2}, {10,8,3}, {1,5,4}, {9,9,5},
            {1,1,6}, {4,6,7}, {6,6,8}, {6,4,9}, {2,6,10}, {1,0,11},
            {7,5,12}, {9,7,13}, {8,5,14}
    };

    auto res = ClosestPair::findClosest(pts);
    if (res.idx1 != -1) {
        cout << "Ближайшая пара: индекс " << res.idx1 << " и " << res.idx2 << "\n";
        cout << "Координаты: (" << pts[res.idx1].x << ", " << pts[res.idx1].y << ") и ("
             << pts[res.idx2].x << ", " << pts[res.idx2].y << ")\n";
        cout << "Минимальное расстояние: " << sqrt(res.dist2) << "\n";
    } else {
        cout << "Пара не найдена\n";
    }
    return 0;
}