Closest Pair (Cặp điểm gần nhất)

Wiki › Thuật toán › Hình học tính toán

Closest Pair (Cặp điểm gần nhất)

huunguyen · Last updated 8, Tháng 4, 2026, 15:31

Tìm cặp điểm gần nhất trong tập $N$ điểm trong $O (N \log N)$ bằng chia để trị hoặc sweep line.

Thuật toán Sweep Line — $O (N \log N)$

Quét từ trái sang phải, duy trì tập điểm trong cửa sổ $[x - d, x]$ với $d$ là khoảng cách nhỏ nhất hiện tại.

#include <bits/stdc++.h>
using namespace std;

struct Point { double x, y; };

double dist(const Point& a, const Point& b) {
    return hypot(a.x-b.x, a.y-b.y);
}

double closest_pair(vector<Point> pts) {
    int n = pts.size();
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });

    double d = 1e18;
    // Set sắp xếp theo y, dùng để tìm điểm trong cửa sổ
    set<pair<double,double>> active;   // {y, x}

    int left = 0;
    for (int i = 0; i < n; i++) {
        // Xóa điểm quá xa về phía trái
        while (left < i && pts[i].x - pts[left].x >= d) {
            active.erase({pts[left].y, pts[left].x});
            left++;
        }

        // Tìm điểm trong cửa sổ [y-d, y+d]
        auto it = active.lower_bound({pts[i].y - d, -1e18});
        while (it != active.end() && it->first <= pts[i].y + d) {
            Point q = {it->second, it->first};
            d = min(d, dist(pts[i], q));
            ++it;
        }

        active.insert({pts[i].y, pts[i].x});
    }
    return d;
}

Thuật toán Chia để trị — $O (N \log N)$

double closest_rec(vector<Point>& pts, int l, int r) {
    if (r - l <= 3) {
        // Brute force cho ≤ 3 điểm
        double d = 1e18;
        for (int i = l; i < r; i++)
            for (int j = i+1; j < r; j++)
                d = min(d, dist(pts[i], pts[j]));
        sort(pts.begin()+l, pts.begin()+r, [](auto& a, auto& b){ return a.y < b.y; });
        return d;
    }

    int mid = (l + r) / 2;
    double mx = pts[mid].x;
    double d = min(closest_rec(pts, l, mid), closest_rec(pts, mid, r));

    // Merge theo y (sau đệ quy, hai nửa đã sắp theo y)
    inplace_merge(pts.begin()+l, pts.begin()+mid, pts.begin()+r,
                  [](auto& a, auto& b){ return a.y < b.y; });

    // Kiểm tra điểm trong dải [mx-d, mx+d]
    vector<Point> strip;
    for (int i = l; i < r; i++)
        if (abs(pts[i].x - mx) < d)
            strip.push_back(pts[i]);

    for (int i = 0; i < (int)strip.size(); i++)
        for (int j = i+1; j < (int)strip.size() && strip[j].y - strip[i].y < d; j++)
            d = min(d, dist(strip[i], strip[j]));

    return d;
}

double closest_pair_dc(vector<Point> pts) {
    sort(pts.begin(), pts.end(), [](auto& a, auto& b){ return a.x < b.x; });
    return closest_rec(pts, 0, pts.size());
}

Khi nào dùng?

Tìm cặp điểm gần nhất trong tập lớn.
Bài toán clustering, gom nhóm điểm.
Làm nền cho các thuật toán geometry phức tạp hơn.

Bình luận

Không có bình luận tại thời điểm này.

Closest Pair (Cặp điểm gần nhất)

Thuật toán Sweep Line — O(NlogN)

Thuật toán Chia để trị — O(NlogN)

Khi nào dùng?

Bình luận

Thuật toán Sweep Line — $O (N \log N)$

Thuật toán Chia để trị — $O (N \log N)$