library/test/aoj/CGL_5_A-Closest_Pair.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/CGL_5_A

Depends on

• library/geometry/2dGeometryTemplate.hpp
• library/geometry/2dPointSet.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/CGL_5_A"
#include <bits/stdc++.h>
using namespace std;
#include "../../geometry/2dPointSet.hpp"
#define ERROR 0.000001

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    Polygon ps(n);
    for(int i=0;i<n;++i) {
        cin>>ps[i];
    }
    cout<<fixed<<setprecision(20)<<closest_pair(ps)<<'\n';
    return 0;
}

#line 1 "library/test/aoj/CGL_5_A-Closest_Pair.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/CGL_5_A"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/geometry/2dGeometryTemplate.hpp"

using Real = double;
using Point = complex<Real>;
using Polygon = vector<Point>;
const Real EPS = 1e-8, PI = acos(-1);

Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}

Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}

istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}

ostream& operator<<(ostream& os, const Point& p) {
    return os << fixed << setprecision(20) << p.real() << " " << p.imag();
}

int sign(const Real& r) {
    if (r <= -EPS) return -1;
    if (r >= +EPS) return +1;
    return 0;
}

bool equals(const Real& a, const Real& b) {
    return sign(a - b) == 0;
}

namespace std {
bool operator<(const Point& a, const Point& b) {
    if (equals(a.real(), b.real())) return a.imag() < b.imag();
    return a.real() < b.real();
}
}  // namespace std

Real dot(const Point& a, const Point& b) {
    return (conj(a) * b).real();
}

Real cross(const Point& a, const Point& b) {
    return (conj(a) * b).imag();
}

struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
};
using Segment = Line;
#line 3 "library/geometry/2dPointSet.hpp"

Real closest_pair(Polygon ps) {
    sort(ps.begin(), ps.end());
    Polygon a(ps.size());

    function<Real(int, int)> rec = [&](int left, int right) -> Real {
        if (right - left <= 1) return 1e18;
        int mid = (left + right) / 2;
        Real x = ps[mid].real();
        Real ret = min(rec(left, mid), rec(mid, right));
        inplace_merge(ps.begin() + left, ps.begin() + mid, ps.begin() + right,
                      [&](const Point& a, const Point& b) { return a.imag() < b.imag(); });
        int pos = 0;
        for (int i = left; i < right; i++) {
            if (fabs((ps[i].real()) - x) >= ret) continue;
            for (int j = 0; j < pos; j++) {
                auto tar = ps[i] - a[pos - j - 1];
                if (tar.imag() >= ret) break;
                ret = min(ret, abs(tar));
            }
            a[pos++] = ps[i];
        }
        return ret;
    };
    return rec(0, (int)ps.size());
}
#line 5 "library/test/aoj/CGL_5_A-Closest_Pair.test.cpp"
#define ERROR 0.000001

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    Polygon ps(n);
    for(int i=0;i<n;++i) {
        cin>>ps[i];
    }
    cout<<fixed<<setprecision(20)<<closest_pair(ps)<<'\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	4 MB
g++	00_sample_01.in	AC	5 ms	4 MB
g++	01_corner_00.in	AC	6 ms	4 MB
g++	01_corner_01.in	AC	6 ms	4 MB
g++	01_corner_02.in	AC	6 ms	4 MB
g++	01_corner_03.in	AC	6 ms	4 MB
g++	02_rand_00.in	AC	6 ms	4 MB
g++	02_rand_01.in	AC	6 ms	4 MB
g++	02_rand_02.in	AC	6 ms	4 MB
g++	02_rand_03.in	AC	6 ms	4 MB
g++	02_rand_04.in	AC	6 ms	4 MB
g++	02_rand_05.in	AC	7 ms	4 MB
g++	02_rand_06.in	AC	13 ms	4 MB
g++	02_rand_07.in	AC	14 ms	4 MB
g++	02_rand_08.in	AC	44 ms	7 MB
g++	02_rand_09.in	AC	80 ms	9 MB
g++	03_line_00.in	AC	50 ms	8 MB
g++	03_line_01.in	AC	53 ms	8 MB
g++	03_line_02.in	AC	35 ms	6 MB
g++	03_line_03.in	AC	35 ms	6 MB
g++	04_linebiased_00.in	AC	58 ms	9 MB
g++	04_linebiased_01.in	AC	61 ms	9 MB
g++	05_grid_00.in	AC	62 ms	9 MB
g++	05_grid_01.in	AC	31 ms	6 MB
g++	05_grid_02.in	AC	70 ms	9 MB
g++	05_grid_03.in	AC	61 ms	8 MB
g++	06_diagonal_00.in	AC	67 ms	9 MB
g++	06_diagonal_01.in	AC	75 ms	9 MB
g++	07_randbiased_00.in	AC	28 ms	5 MB
g++	07_randbiased_01.in	AC	20 ms	5 MB
g++	07_randbiased_02.in	AC	79 ms	9 MB
g++	07_randbiased_03.in	AC	80 ms	9 MB

Back to top page