Two-nearest-points-distance-search

nearest_points.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using dist_2_t = uint64_t;
using point = std::pair<int, int>;

dist_2_t get_dist_2(const point &p1, const point &p2) {
    dist_2_t dx = p1.first - p2.first;
    dist_2_t dy = p1.second - p2.second;
    return dx * dx + dy * dy;
}

bool comp_y(const point &p1, const point &p2) {
    return p1.second < p2.second;
}

unsigned long long get_min_dist_2(std::vector<point> &points, size_t idx_l, size_t idx_r) {
    assert(idx_r > idx_l + 1);

    if (idx_r - idx_l < 4) {
        auto ans = get_dist_2(points[idx_l], points[idx_l + 1]);
        for (int i = idx_l; i < idx_r; ++i) {
            for (int j = i + 1; j < idx_r; ++j) {
                ans = std::min(get_dist_2(points[i], points[j]), ans);
            }
        }
        std::sort(points.begin() + idx_l, points.begin() + idx_r, comp_y);
        return ans;
    }

    size_t mid = (idx_l + idx_r) / 2;
    auto mid_x = points[mid].first;

    dist_2_t curr_ans = std::min(
            get_min_dist_2(points, idx_l, mid),
            get_min_dist_2(points, mid, idx_r)
    );

    std::inplace_merge(
            points.begin() + idx_l, points.begin() + mid, points.begin() + idx_r, comp_y
    );

    std::vector<point> close_to_mid;
    std::copy_if(
            points.begin() + idx_l, points.begin() + idx_r,
            std::back_inserter(close_to_mid),
            [mid_x, curr_ans](const point &p) {
                dist_2_t dx = abs(p.first - mid_x);
                return dx * dx <= curr_ans;
            }
    );

    for (size_t i = 0; i < close_to_mid.size(); ++i) {
        for (size_t j = i; j > 0; --j) {
            auto dy = close_to_mid[i].second - close_to_mid[j - 1].second;
            if (dy * dy >= curr_ans) {
                break;
            }
            curr_ans = std::min(curr_ans, get_dist_2(close_to_mid[i], close_to_mid[j - 1]));
        }
    }

    return curr_ans;
}

dist_2_t solve(std::vector<point>& points) {
    std::sort(points.begin(), points.end());
    return get_min_dist_2(points, 0, points.size());
}


#define TEST false

int main() {
#if TEST
    // Simple test

    constexpr int N_ITERATIONS = 100000;
    for (int iter = 0; iter < N_ITERATIONS; ++iter) {
        if (iter % 100 == 99) {
            std::cout << "Iter #" << iter + 1 << std::endl;
        }

        int n = rand() % 100 + 3; // [3...102]

        std::vector<point> points;
        while (n --> 0) {
            int x = rand() % 1000 - 500;
            int y = rand() % 1000 - 500; // x, y in [-500, 499]
            points.emplace_back(x, y);
        }

        dist_2_t expected = std::numeric_limits<dist_2_t>::max();
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                expected = std::min(get_dist_2(points[i], points[j]), expected);
            }
        }

        assert(solve(points) == expected);
    }
    std::cout << "All tests passed!" << std::endl;

#else
    int n;
    std::vector<point> points;
    std::cin >> n;
    points.reserve(n);
    while (n --> 0) {
        int x, y;
        std::cin >> x >> y;
        points.emplace_back(x, y);
    }
    std::cout << solve(points) << std::endl;
#endif

    return 0;
}