cp-documentation
This documentation is automatically generated by online-judge-tools/verification-helper
Test/LC/closest_pair.test.cpp
- View this file on GitHub
- Last update: 2025-07-02 20:11:36+09:00
- Problem: https://judge.yosupo.jp/problem/closest_pair
Depends on
- Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp
- Src/GeometryZ2/Distance/PointAndPoint.hpp
- Src/GeometryZ2/Point.hpp
- Src/GeometryZ2/PointCloud.hpp
- Src/GeometryZ2/Zahlen.hpp
- 標準データ型のエイリアス
(Src/Template/TypeAlias.hpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/closest_pair"
#include "../../Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp"
using namespace zawa;
using namespace geometryZ2;
#include <iostream>
#include <utility>
std::pair<int, int> solve() {
int N;
std::cin >> N;
PointCloud P(N);
for (auto& p : P) std::cin >> p;
return ClosestPairOfPoints<int>(P);
}
int main() {
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::ios::sync_with_stdio(false);
int T;
std::cin >> T;
while (T--) {
auto [i, j] = solve();
std::cout << i << ' ' << j << '\n';
}
}#line 1 "Test/LC/closest_pair.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/closest_pair"
#line 2 "Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp"
#line 2 "Src/GeometryZ2/PointCloud.hpp"
#line 2 "Src/GeometryZ2/Point.hpp"
#line 2 "Src/Template/TypeAlias.hpp"
#include <cstdint>
#include <cstddef>
namespace zawa {
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using usize = std::size_t;
} // namespace zawa
#line 2 "Src/GeometryZ2/Zahlen.hpp"
#line 4 "Src/GeometryZ2/Zahlen.hpp"
#include <cassert>
namespace zawa {
namespace geometryZ2 {
using Zahlen = i64;
namespace internal {
constexpr i32 positive{1};
constexpr i32 zero{0};
constexpr i32 negative{-1};
} // namespace internal
constexpr i32 Sign(Zahlen value) {
if (value < 0) return internal::negative;
if (value > 0) return internal::positive;
return internal::zero;
}
constexpr bool Positive(Zahlen value) {
return Sign(value) == internal::positive;
}
constexpr bool Zero(Zahlen value) {
return Sign(value) == internal::zero;
}
constexpr bool Negative(Zahlen value) {
return Sign(value) == internal::negative;
}
constexpr Zahlen Abs(Zahlen value) {
return (value > 0 ? value : -value);
}
constexpr Zahlen Square(Zahlen value) {
return value * value;
}
} // namespace geometryZ2
} // namespace zawa
#line 5 "Src/GeometryZ2/Point.hpp"
#include <algorithm>
#include <iostream>
#line 9 "Src/GeometryZ2/Point.hpp"
#include <limits>
namespace zawa {
namespace geometryZ2 {
class Point {
private:
Zahlen x_{}, y_{};
static constexpr i32 origin{0};
static constexpr i32 firstQuadrant{1};
static constexpr i32 secondQuadrant{2};
static constexpr i32 thirdQuadrant{-2};
static constexpr i32 forthQuadrant{-1};
public:
/* constructor */
Point() = default;
Point(const Point& p) : x_{p.x()}, y_{p.y()} {}
Point(Zahlen x, Zahlen y) : x_{x}, y_{y} {}
/* getter setter */
Zahlen& x() {
return x_;
}
const Zahlen& x() const {
return x_;
}
Zahlen& y() {
return y_;
}
const Zahlen& y() const {
return y_;
}
/* operator */
Point& operator=(const Point& p) {
x() = p.x();
y() = p.y();
return *this;
}
Point& operator+=(const Point& p) {
x() += p.x();
y() += p.y();
return *this;
}
friend Point operator+(const Point& p0, const Point& p1) {
return Point{p0} += p1;
}
Point& operator-=(const Point& p) {
x() -= p.x();
y() -= p.y();
return *this;
}
friend Point operator-(const Point& p0, const Point& p1) {
return Point{p0} -= p1;
}
Point& operator*=(Zahlen k) {
x() *= k;
y() *= k;
return *this;
}
friend Point operator*(const Point& p, Zahlen k) {
return Point{p} *= k;
}
friend Point operator*(Zahlen k, const Point& p) {
return Point{p} *= k;
}
Point& operator/=(Zahlen k) {
assert(k);
assert(x() % k == 0);
assert(y() % k == 0);
x() /= k;
y() /= k;
return *this;
}
friend Point operator/(const Point& p, Zahlen k) {
return Point{p} /= k;
}
friend bool operator==(const Point& p0, const Point& p1) {
return p0.x() == p1.x() and p0.y() == p1.y();
}
friend bool operator!=(const Point& p0, const Point& p1) {
return p0.x() != p1.x() or p0.y() != p1.y();
}
friend bool operator<(const Point& p0, const Point& p1) {
if (p0.x() != p1.x()) return p0.x() < p1.x();
else return p0.y() < p1.y();
}
friend bool operator<=(const Point& p0, const Point& p1) {
return (p0 < p1) or (p0 == p1);
}
friend bool operator>(const Point& p0, const Point& p1) {
if (p0.x() != p1.x()) return p0.x() > p1.x();
else return p0.y() > p1.y();
}
friend bool operator>=(const Point& p0, const Point& p1) {
return (p0 > p1) or (p0 == p1);
}
friend std::istream& operator>>(std::istream& is, Point& p) {
is >> p.x() >> p.y();
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Point& p) {
os << '(' << p.x() << ',' << p.y() << ')';
return os;
}
/* member function */
Zahlen normSquare() const {
return Square(x()) + Square(y());
}
bool isNormSquareOver(Zahlen d) const {
assert(!Negative(d));
auto [mn, mx]{std::minmax({ Abs(x()), Abs(y()) })};
if (mx and mx > d / mx) {
return true;
}
long long s1{Square(mn)}, s2{Square(mx)};
if (s1 > d - s2) {
return true;
}
return false;
}
bool isNormSquareOverflow() const {
return isNormSquareOver(std::numeric_limits<Zahlen>::max());
}
i32 area() const {
if (x_ == 0 and y_ == 0) return origin;
if (x_ <= 0 and y_ < 0) return thirdQuadrant;
if (x_ > 0 and y_ <= 0) return forthQuadrant;
if (x_ >= 0 and y_ > 0) return firstQuadrant;
return secondQuadrant;
}
/* static member */
static bool ArgComp(const Point& p0, const Point& p1) {
if (p0.area() != p1.area()) return p0.area() < p1.area();
Zahlen cross{Cross(p0, p1)};
return (!Zero(cross) ? Positive(cross) : p0.normSquare() < p1.normSquare());
}
/* friend function */
friend Zahlen Dot(const Point& p0, const Point& p1) {
return p0.x() * p1.x() + p0.y() * p1.y();
}
friend Zahlen Cross(const Point& p0, const Point& p1) {
return p0.x() * p1.y() - p0.y() * p1.x();
}
};
using Vector = Point;
} // namespace geometryZ2
} // namespace zawa
#line 4 "Src/GeometryZ2/PointCloud.hpp"
#line 6 "Src/GeometryZ2/PointCloud.hpp"
#include <vector>
namespace zawa {
namespace geometryZ2 {
using PointCloud = std::vector<Point>;
void ArgSort(PointCloud& p) {
std::sort(p.begin(), p.end(), Point::ArgComp);
}
} // namespace geometryZ2
} // namespace zawa
#line 2 "Src/GeometryZ2/Distance/PointAndPoint.hpp"
#line 5 "Src/GeometryZ2/Distance/PointAndPoint.hpp"
namespace zawa {
namespace geometryZ2 {
Zahlen DistanceSquare(const Point& p0, const Point& p1) {
return Vector{p1 - p0}.normSquare();
}
} // namespace geometryZ2
} // namespace zawa
#line 5 "Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp"
#line 8 "Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp"
#include <concepts>
#include <ranges>
#include <utility>
#line 12 "Src/GeometryZ2/Distance/ClosestPairOfPoints.hpp"
namespace zawa {
namespace geometryZ2 {
template <std::integral T = usize>
std::pair<T, T> ClosestPairOfPoints(PointCloud P) {
assert(std::ssize(P) >= 2);
std::vector<std::pair<Point, T>> ps(P.size());
for (usize i = 0 ; i < P.size() ; i++) {
ps[i].first = std::move(P[i]);
ps[i].second = i;
}
std::ranges::sort(ps);
usize mini = ps[0].second, minj = ps[1].second;
Zahlen mind = DistanceSquare(ps[0].first, ps[1].first);
auto rec = [&](auto rec, usize l, usize r) -> void {
if (r - l <= 1) return;
const usize m = (l + r) >> 1;
const Zahlen midx = ps[m].first.x();
rec(rec, l, m);
rec(rec, m, r);
std::inplace_merge(ps.begin() + l, ps.begin() + m, ps.begin() + r,
[](const auto& i, const auto& j) { return i.first.y() < j.first.y(); });
std::vector<usize> near;
near.reserve(r - l);
for (usize i = l ; i < r ; i++) {
const Zahlen ix = ps[i].first.x(), iy = ps[i].first.y();
const T idx = ps[i].second;
if (Square(ix - midx) > mind) continue;
for (usize j : near | std::views::reverse) {
const Zahlen jx = ps[j].first.x(), jy = ps[j].first.y();
const T jdx = ps[j].second;
if (Square(iy - jy) >= mind) break;
if (Square(ix - jx) + Square(iy - jy) < mind) {
mini = idx;
minj = jdx;
mind = Square(ix - jx) + Square(iy - jy);
}
}
near.push_back(i);
}
};
rec(rec, 0, ps.size());
return {mini, minj};
}
} // namespace geometryZ2
} // namespace zawa
#line 4 "Test/LC/closest_pair.test.cpp"
using namespace zawa;
using namespace geometryZ2;
#line 9 "Test/LC/closest_pair.test.cpp"
std::pair<int, int> solve() {
int N;
std::cin >> N;
PointCloud P(N);
for (auto& p : P) std::cin >> p;
return ClosestPairOfPoints<int>(P);
}
int main() {
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::ios::sync_with_stdio(false);
int T;
std::cin >> T;
while (T--) {
auto [i, j] = solve();
std::cout << i << ' ' << j << '\n';
}
}