Closest Pair of Points (verify/geometry/closest_pair.test.cpp)

• View this file on GitHub
• Last update: 2024-11-21 23:45:42+01:00
• Problem: https://judge.yosupo.jp/problem/closest_pair

Depends on

• cp-algo/geometry/closest_pair.hpp
• cp-algo/geometry/point.hpp
• cp-algo/random/rng.hpp
• cp-algo/util/complex.hpp

Code

// @brief Closest Pair of Points
#define PROBLEM "https://judge.yosupo.jp/problem/closest_pair"
#pragma GCC optimize("Ofast,unroll-loops")
#include "cp-algo/geometry/closest_pair.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;

void solve() {
    int n;
    cin >> n;
    vector<point> r(n);
    for(auto &it: r) {
        it.read();
    }
    auto [a, b] = closest_pair(r);
    cout << a << ' ' << b << "\n";
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#line 1 "verify/geometry/closest_pair.test.cpp"
// @brief Closest Pair of Points
#define PROBLEM "https://judge.yosupo.jp/problem/closest_pair"
#pragma GCC optimize("Ofast,unroll-loops")
#line 1 "cp-algo/geometry/closest_pair.hpp"


#line 1 "cp-algo/random/rng.hpp"


#include <chrono>
#include <random>
namespace cp_algo::random {
    uint64_t rng() {
        static std::mt19937_64 rng(
            std::chrono::steady_clock::now().time_since_epoch().count()
        );
        return rng();
    }
}

#line 1 "cp-algo/geometry/point.hpp"


#line 1 "cp-algo/util/complex.hpp"


#include <cmath>
namespace cp_algo {
    // Custom implementation, since std::complex is UB on non-floating types
    template<typename T>
    struct complex {
        using value_type = T;
        T x, y;
        constexpr complex() {}
        constexpr complex(T x): x(x), y(0) {}
        constexpr complex(T x, T y): x(x), y(y) {}
        complex& operator *= (T t) {x *= t; y *= t; return *this;}
        complex& operator /= (T t) {x /= t; y /= t; return *this;}
        complex operator * (T t) const {return complex(*this) *= t;}
        complex operator / (T t) const {return complex(*this) /= t;}
        complex& operator += (complex t) {x += t.x; y += t.y; return *this;}
        complex& operator -= (complex t) {x -= t.x; y -= t.y; return *this;}
        complex operator * (complex t) const {return {x * t.x - y * t.y, x * t.y + y * t.x};}
        complex operator / (complex t) const {return *this * t.conj() / t.norm();}
        complex operator + (complex t) const {return complex(*this) += t;}
        complex operator - (complex t) const {return complex(*this) -= t;}
        complex& operator *= (complex t) {return *this = *this * t;}
        complex& operator /= (complex t) {return *this = *this / t;}
        complex operator - () const {return {-x, -y};}
        complex conj() const {return {x, -y};}
        T norm() const {return x * x + y * y;}
        T abs() const {return std::sqrt(norm());}
        T real() const {return x;}
        T imag() const {return y;}
        T& real() {return x;}
        T& imag() {return y;}
        static complex polar(T r, T theta) {return {r * cos(theta), r * sin(theta)};}
        auto operator <=> (complex const& t) const = default;
    };
    template<typename T>
    complex<T> operator * (auto x, complex<T> y) {return y *= x;}
    template<typename T> complex<T> conj(complex<T> x) {return x.conj();}
    template<typename T> T norm(complex<T> x) {return x.norm();}
    template<typename T> T abs(complex<T> x) {return x.abs();}
    template<typename T> T& real(complex<T> &x) {return x.real();}
    template<typename T> T& imag(complex<T> &x) {return x.imag();}
    template<typename T> T real(complex<T> const& x) {return x.real();}
    template<typename T> T imag(complex<T> const& x) {return x.imag();}
    template<typename T> complex<T> polar(T r, T theta) {return complex<T>::polar(r, theta);}
}

#line 4 "cp-algo/geometry/point.hpp"
#include <iostream>
namespace cp_algo::geometry {
    template<typename ftype>
    struct point_t: complex<ftype> {
        using Base = complex<ftype>;
        using Base::Base;

        point_t(Base const& t): Base(t) {}
        
        auto operator <=> (point_t const& t) const {
            return std::pair{y(), -x()} <=> std::pair{t.y(), -t.x()};
        }

        ftype x() const {return Base::real();}
        ftype y() const {return Base::imag();}

        point_t cmul(point_t const& t) const {return conj(*this) * t;}
        ftype dot(point_t const& t) const {return cmul(t).x();}
        ftype cross(point_t const& t) const {return cmul(t).y();}

        static constexpr point_t O = {0, 0};

        int half() const {
            return *this < O ? -1 : *this == O ? 0 : 1;
        }

        static bool ccw(point_t const& a, point_t const& b) {
            return a.cross(b) > 0;
        }
        static bool ccw_abs(point_t const& a, point_t const & b) {
            return std::tuple{a.half(), (ftype)0, norm(a)} <
                   std::tuple{b.half(), a.cross(b), norm(b)};
        }
        void read() {
            ftype _x, _y;
            std::cin >> _x >> _y;
            *this = {_x, _y};
        }
        void print() const {
            std::cout << x() << ' ' << y() << "\n";
        }
    };
}

#line 5 "cp-algo/geometry/closest_pair.hpp"
#include <vector>
#include <map>
namespace cp_algo::geometry {
    // Rabin & Lipton
    template<typename ftype>
    auto closest_pair(std::vector<point_t<ftype>> const& r) {
        using point = point_t<ftype>;
        size_t n = size(r);
        int64_t md = 1e18;
        for(size_t i = 0; i < n / 100; i++) {
            auto A = random::rng() % n;
            auto B = random::rng() % n;
            if(A != B) {
                md = std::min(md, norm(r[A] - r[B]));
                if(md == 0) {
                    return std::pair{A, B};
                }
            }
        }
        std::map<point, std::vector<size_t>> neigs;
        md = (int64_t)ceil(sqrt((double)md));
        for(size_t i = 0; i < n; i++) {
            neigs[r[i] / md].push_back(i);
        }
        size_t a = 0, b = 1;
        md = norm(r[a] - r[b]);
        for(auto &[p, id]: neigs) {
            for(int dx: {-1, 0, 1}) {
                for(int dy: {-1, 0, 1}) {
                    auto pp = p + point{dx, dy};
                    if(!neigs.count(pp)) {
                        continue;
                    }
                    for(size_t i: neigs[pp]) {
                        for(size_t j: id) {
                            if(j == i) {
                                break;
                            }
                            int64_t cur = norm(r[i] - r[j]);
                            if(cur < md) {
                                md = cur;
                                a = i;
                                b = j;
                            }
                        }
                    }
                }
            }
        }
        return std::pair{a, b};
    }
}

#line 5 "verify/geometry/closest_pair.test.cpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::geometry;
using point = point_t<int64_t>;

void solve() {
    int n;
    cin >> n;
    vector<point> r(n);
    for(auto &it: r) {
        it.read();
    }
    auto [a, b] = closest_pair(r);
    cout << a << ' ' << b << "\n";
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	63 ms	4 MB
g++	example_00	AC	4 ms	4 MB
g++	fix_near_grid_00	AC	313 ms	19 MB
g++	fix_near_grid_01	AC	363 ms	18 MB
g++	max_colinear_00	AC	264 ms	19 MB
g++	max_colinear_01	AC	272 ms	24 MB
g++	max_random_00	AC	344 ms	21 MB
g++	max_random_01	AC	48 ms	11 MB
g++	max_random_02	AC	622 ms	19 MB
g++	max_random_03	AC	389 ms	29 MB
g++	max_random_04	AC	505 ms	37 MB
g++	max_random_05	AC	47 ms	11 MB
g++	max_random_06	AC	345 ms	20 MB
g++	max_random_07	AC	312 ms	22 MB
g++	mid_random_00	AC	304 ms	4 MB
g++	mid_random_01	AC	287 ms	4 MB
g++	mid_random_02	AC	288 ms	4 MB
g++	near_circle_00	AC	260 ms	23 MB
g++	near_circle_01	AC	402 ms	18 MB
g++	near_grid_00	AC	335 ms	19 MB
g++	near_grid_01	AC	514 ms	18 MB
g++	small_random_00	AC	89 ms	4 MB
g++	small_random_01	AC	67 ms	4 MB
g++	small_random_02	AC	68 ms	4 MB
g++	small_random_03	AC	66 ms	4 MB
g++	small_random_04	AC	88 ms	4 MB
g++	small_random_05	AC	67 ms	4 MB
g++	small_random_06	AC	66 ms	4 MB
g++	small_random_07	AC	67 ms	4 MB

Back to top page