This documentation is automatically generated by competitive-verifier/competitive-verifier
// @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 4 "cp-algo/geometry/point.hpp"
#include <iostream>
#include <complex>
namespace cp_algo::geometry {
template<typename ftype>
struct point_t: public std::complex<ftype> {
using Base = std::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<int>> neigs;
md = ceil(sqrtl(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();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | all_same_00 | AC | 55 ms | 4 MB |
g++ | example_00 | AC | 5 ms | 4 MB |
g++ | fix_near_grid_00 | AC | 630 ms | 65 MB |
g++ | fix_near_grid_01 | AC | 460 ms | 14 MB |
g++ | max_colinear_00 | AC | 392 ms | 14 MB |
g++ | max_colinear_01 | AC | 288 ms | 17 MB |
g++ | max_random_00 | AC | 372 ms | 18 MB |
g++ | max_random_01 | AC | 45 ms | 11 MB |
g++ | max_random_02 | AC | 492 ms | 29 MB |
g++ | max_random_03 | AC | 351 ms | 19 MB |
g++ | max_random_04 | AC | 558 ms | 16 MB |
g++ | max_random_05 | AC | 45 ms | 11 MB |
g++ | max_random_06 | AC | 450 ms | 17 MB |
g++ | max_random_07 | AC | 718 ms | 16 MB |
g++ | mid_random_00 | AC | 336 ms | 4 MB |
g++ | mid_random_01 | AC | 321 ms | 4 MB |
g++ | mid_random_02 | AC | 322 ms | 4 MB |
g++ | near_circle_00 | AC | 301 ms | 21 MB |
g++ | near_circle_01 | AC | 433 ms | 15 MB |
g++ | near_grid_00 | AC | 670 ms | 63 MB |
g++ | near_grid_01 | AC | 220 ms | 17 MB |
g++ | small_random_00 | AC | 83 ms | 4 MB |
g++ | small_random_01 | AC | 65 ms | 4 MB |
g++ | small_random_02 | AC | 65 ms | 4 MB |
g++ | small_random_03 | AC | 65 ms | 4 MB |
g++ | small_random_04 | AC | 82 ms | 4 MB |
g++ | small_random_05 | AC | 66 ms | 4 MB |
g++ | small_random_06 | AC | 64 ms | 4 MB |
g++ | small_random_07 | AC | 65 ms | 4 MB |