sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A" #define ERROR 0.000001 #include "../../geometry/geometry.hpp" #include "../../geometry/closest_pair.hpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int n; cin >> n; vector<Vec> pts(n); for (auto& p : pts) cin >> p; cout << closest_pair(pts) << endl; }
#line 1 "test/aoj/CGL_5_A.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A" #define ERROR 0.000001 #line 2 "geometry/geometry.hpp" #include <algorithm> #include <cassert> #include <cmath> #include <complex> #include <iostream> #include <numbers> #include <numeric> #include <vector> // note that if T is of an integer type, std::abs does not work using T = double; using Vec = std::complex<T>; std::istream& operator>>(std::istream& is, Vec& p) { T x, y; is >> x >> y; p = {x, y}; return is; } T dot(const Vec& a, const Vec& b) { return (std::conj(a) * b).real(); } T cross(const Vec& a, const Vec& b) { return (std::conj(a) * b).imag(); } constexpr T PI = std::numbers::pi_v<T>; constexpr T eps = 1e-10; inline bool eq(T a, T b) { return std::abs(a - b) <= eps; } inline bool eq(Vec a, Vec b) { return std::abs(a - b) <= eps; } inline bool lt(T a, T b) { return a < b - eps; } inline bool leq(T a, T b) { return a <= b + eps; } struct Line { Vec p1, p2; Line() = default; Line(const Vec& p1, const Vec& p2) : p1(p1), p2(p2) {} Vec dir() const { return p2 - p1; } }; struct Segment : Line { using Line::Line; }; struct Circle { Vec c; T r; Circle() = default; Circle(const Vec& c, T r) : c(c), r(r) {} }; using Polygon = std::vector<Vec>; Vec rot(const Vec& a, T ang) { return a * Vec(std::cos(ang), std::sin(ang)); } Vec perp(const Vec& a) { return Vec(-a.imag(), a.real()); } Vec projection(const Line& l, const Vec& p) { return l.p1 + dot(p - l.p1, l.dir()) * l.dir() / std::norm(l.dir()); } Vec reflection(const Line& l, const Vec& p) { return T(2) * projection(l, p) - p; } // 0: collinear // 1: counter-clockwise // -1: clockwise int ccw(const Vec& a, const Vec& b, const Vec& c) { if (eq(cross(b - a, c - a), 0)) return 0; if (lt(cross(b - a, c - a), 0)) return -1; return 1; } void sort_by_arg(std::vector<Vec>& pts) { std::ranges::sort(pts, [&](auto& p, auto& q) { if ((p.imag() < 0) != (q.imag() < 0)) return (p.imag() < 0); if (cross(p, q) == 0) { if (p == Vec(0, 0)) return !(q.imag() < 0 || (q.imag() == 0 && q.real() > 0)); if (q == Vec(0, 0)) return (p.imag() < 0 || (p.imag() == 0 && p.real() > 0)); return (p.real() > q.real()); } return (cross(p, q) > 0); }); } #line 3 "geometry/closest_pair.hpp" #include <ranges> #line 5 "geometry/closest_pair.hpp" #line 7 "geometry/closest_pair.hpp" /** * @brief Closest Pair */ T closest_pair(std::vector<Vec>& pts) { std::ranges::sort(pts, {}, [](const Vec& v) { return v.real(); }); auto rec = [&](const auto& rec, int l, int r) -> T { if (r - l <= 1) return std::numeric_limits<T>::max(); int m = std::midpoint(l, r); T x = pts[m].real(); T d = std::min(rec(rec, l, m), rec(rec, m, r)); std::ranges::inplace_merge(pts.begin() + l, pts.begin() + m, pts.begin() + r, {}, [](const Vec& v) { return v.imag(); }); std::vector<Vec> b; for (int i = l; i < r; ++i) { if (leq(d, std::abs(pts[i].real() - x))) continue; for (auto& p : b | std::views::reverse) { if (leq(d, std::abs(pts[i].imag() - p.imag()))) break; d = std::min(d, std::abs(pts[i] - p)); } b.push_back(pts[i]); } return d; }; return rec(rec, 0, pts.size()); } #line 6 "test/aoj/CGL_5_A.test.cpp" #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int n; cin >> n; vector<Vec> pts(n); for (auto& p : pts) cin >> p; cout << closest_pair(pts) << endl; }