Closest Pair
(geometry/closest_pair.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

平面上の整数点集合から、距離が最小の 2 点の元の添字を返す。 分割統治で解き、計算量は $O(N log N)$。

できること

• pair<int, int> closest_pair(const vector<pair<long long, long long>>& points) 最短距離を持つ 2 点の添字を返す。points.size() < 2 は想定しない

使い方

入力順を保ったまま点列を渡すと、返り値はその元の添字になる。 同じ座標の点が複数あってもよい。

実装上の補足

• 距離比較は二乗距離で行うので平方根は使わない
• 差の二乗が 64 bit を超える可能性があるため、内部計算は __int128_t を使う
• 複数の最短対があるとき、どれを返すかは規定しない

Verified with

• test/yosupo_closest_pair.test.cpp

Code

pair<int, int> closest_pair(const vector<pair<long long, long long>> &points) {
    using Dist = __int128_t;
    struct P {
        long long x;
        long long y;
        int idx;
    };

    int n = points.size();
    assert(n >= 2);
    vector<P> ps(n);
    for (int i = 0; i < n; ++i) {
        ps[i] = {points[i].first, points[i].second, i};
    }
    sort(ps.begin(), ps.end(), [](const P &a, const P &b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        return a.idx < b.idx;
    });

    Dist best = -1;
    pair<int, int> ans = {-1, -1};
    auto update = [&](const P &a, const P &b) {
        Dist dx = Dist(a.x) - Dist(b.x);
        Dist dy = Dist(a.y) - Dist(b.y);
        Dist d = dx * dx + dy * dy;
        pair<int, int> cand = {a.idx, b.idx};
        if (best == -1 || d < best) {
            best = d;
            ans = cand;
        }
    };
    update(ps[0], ps[1]);

    auto dfs = [&](auto &&self, int l, int r) -> vector<int> {
        if (r - l == 1) return {l};
        int m = (l + r) >> 1;
        long long mx = ps[m].x;
        vector<int> left = self(self, l, m);
        vector<int> right = self(self, m, r);
        vector<int> ord;
        vector<int> near;
        ord.reserve(r - l);
        near.reserve(r - l);
        int i = 0, j = 0;
        while (i < (int)left.size() || j < (int)right.size()) {
            int idx;
            if (j == (int)right.size() || (i < (int)left.size() && ps[left[i]].y < ps[right[j]].y)) {
                idx = left[i++];
            } else {
                idx = right[j++];
            }
            ord.push_back(idx);
            Dist dx = Dist(ps[idx].x) - Dist(mx);
            if (dx * dx > best) continue;
            for (int k = (int)near.size() - 1; k >= 0; --k) {
                int idy = near[k];
                Dist dy = Dist(ps[idx].y) - Dist(ps[idy].y);
                if (best == 0 || dy * dy > best) break;
                update(ps[idx], ps[idy]);
            }
            near.push_back(idx);
        }
        return ord;
    };
    dfs(dfs, 0, n);
    return ans;
}

/**
 * @brief Closest Pair
 */

#line 1 "geometry/closest_pair.cpp"
pair<int, int> closest_pair(const vector<pair<long long, long long>> &points) {
    using Dist = __int128_t;
    struct P {
        long long x;
        long long y;
        int idx;
    };

    int n = points.size();
    assert(n >= 2);
    vector<P> ps(n);
    for (int i = 0; i < n; ++i) {
        ps[i] = {points[i].first, points[i].second, i};
    }
    sort(ps.begin(), ps.end(), [](const P &a, const P &b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        return a.idx < b.idx;
    });

    Dist best = -1;
    pair<int, int> ans = {-1, -1};
    auto update = [&](const P &a, const P &b) {
        Dist dx = Dist(a.x) - Dist(b.x);
        Dist dy = Dist(a.y) - Dist(b.y);
        Dist d = dx * dx + dy * dy;
        pair<int, int> cand = {a.idx, b.idx};
        if (best == -1 || d < best) {
            best = d;
            ans = cand;
        }
    };
    update(ps[0], ps[1]);

    auto dfs = [&](auto &&self, int l, int r) -> vector<int> {
        if (r - l == 1) return {l};
        int m = (l + r) >> 1;
        long long mx = ps[m].x;
        vector<int> left = self(self, l, m);
        vector<int> right = self(self, m, r);
        vector<int> ord;
        vector<int> near;
        ord.reserve(r - l);
        near.reserve(r - l);
        int i = 0, j = 0;
        while (i < (int)left.size() || j < (int)right.size()) {
            int idx;
            if (j == (int)right.size() || (i < (int)left.size() && ps[left[i]].y < ps[right[j]].y)) {
                idx = left[i++];
            } else {
                idx = right[j++];
            }
            ord.push_back(idx);
            Dist dx = Dist(ps[idx].x) - Dist(mx);
            if (dx * dx > best) continue;
            for (int k = (int)near.size() - 1; k >= 0; --k) {
                int idy = near[k];
                Dist dy = Dist(ps[idx].y) - Dist(ps[idy].y);
                if (best == 0 || dy * dy > best) break;
                update(ps[idx], ps[idy]);
            }
            near.push_back(idx);
        }
        return ord;
    };
    dfs(dfs, 0, n);
    return ans;
}

/**
 * @brief Closest Pair
 */

Back to top page