Wiki › Thuật toán › Hình học tính toán › Closest Pair (Cặp điểm gần nhất)

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

huunguyen Updated Tháng sáu 2, 2026

Bài toán cặp điểm gần nhất (closest pair of points): cho $N$ điểm trên mặt phẳng, tìm hai điểm có khoảng cách Euclid nhỏ nhất. Cách ngây thơ là xét mọi cặp, mất $O (N^{2})$ — với $N = 10^{5}$ là khoảng $10^{10}$ phép tính, quá chậm. Bằng chia để trị hoặc quét đường (sweep line) kết hợp một cấu trúc có thứ tự, ta giải được trong $O (N \log N)$ .

Ý tưởng / Trực giác

Mấu chốt của bài là: khi đã biết một khoảng cách tốt $d$ , ta không cần xét những cặp điểm cách nhau quá $d$ . Nếu hai điểm cách nhau hơn $d$ theo riêng trục $x$ (hoặc riêng trục $y$ ) thì chắc chắn khoảng cách thật của chúng $\geq d$ , nên bỏ qua được. Cả hai thuật toán dưới đây đều khai thác đúng tính chất này để cắt số cặp cần xét từ $O (N^{2})$ xuống $O (N)$ .

Chia để trị. Sắp các điểm theo $x$ , chia đôi bằng một đường thẳng đứng $x = m_{x}$ . Gọi $d_{L}, d_{R}$ là đáp án của nửa trái và nửa phải, đặt $d = min (d_{L}, d_{R})$ . Cặp gần nhất tổng thể hoặc nằm gọn một bên (đã tính), hoặc vắt ngang đường chia. Cặp vắt ngang nếu tốt hơn $d$ thì cả hai điểm phải nằm trong dải (strip) rộng $2 d$ quanh đường chia: $| x - m_{x} | < d$ . Điều kỳ diệu: bên trong dải đó, nếu sắp theo $y$ , thì mỗi điểm chỉ cần so với một số hằng các điểm kế tiếp (có $y$ cách nó dưới $d$ ). Lý do hình học: trong một hình chữ nhật $2 d \times d$ không thể nhét quá $O (1)$ điểm mà đôi một cách nhau $\geq d$ (thực tế tối đa 8 điểm), nên mỗi điểm chỉ cần nhìn xuống vài điểm phía sau.

Sweep line. Quét các điểm theo $x$ tăng dần, giữ trong một set (sắp theo $y$ ) những điểm có hoành độ nằm trong khoảng $[x_{i} - d, x_{i}]$ — gọi là cửa sổ hoạt động. Khi xử lý điểm $i$ , mọi ứng viên tốt hơn $d$ phải có $x$ cách $x_{i}$ dưới $d$ (đã đảm bảo bởi cửa sổ) và có $y$ trong $[y_{i} - d, y_{i} + d]$ (tra nhanh bằng lower_bound trên set). Lại theo lập luận hình chữ nhật ở trên, số điểm trong dải đó chỉ là hằng. Mỗi điểm vào/ra set đúng một lần.

Ví dụ chạy tay (sweep line)

Xét 6 điểm, đã sắp theo $x$ :

   A(0,0)  B(1,4)  C(2,1)  D(3,3)  E(5,2)  F(6,4)

Vẽ trên lưới (cột = x, hàng = y):

 y
 4 | . B . . . F
 3 | . . . D . .
 2 | . . . . E .
 1 | . . C . . .
 0 | A . . . . .
   +-------------- x
     0 1 2 3 4 5 6

Quét trái→phải, d khởi tạo $+ \infty$ , set theo $y$ là cửa sổ hoạt động:

Bước	Điểm	Cửa sổ (loại điểm có $x_{i} - x < d$ )	So với	Cập nhật $d$
1	A(0,0)	{A}	—	$\infty$
2	B(1,4)	{A,B}	A: $\sqrt{1 + 16} \approx 4.12$	$d = 4.12$
3	C(2,1)	{A,B,C}	A: $\sqrt{4 + 1} \approx 2.24$ ; B: $\sqrt{1 + 9} \approx 3.16$	$d = 2.24$
4	D(3,3)	C,D (A,B bị đẩy ra vì $3 - x \geq d$ )	C: $\sqrt{1 + 4} \approx 2.24$	$d = 2.24$
5	E(5,2)	E (mọi điểm cũ cách $> d$ )	—	$d = 2.24$
6	F(6,4)	E,F	E: $\sqrt{1 + 4} \approx 2.24$	$d = 2.24$

Tại bước 4, trước khi xét D ta đẩy A, B ra khỏi cửa sổ vì $x_{D} - x = 3 - 0, 3 - 1 \geq d = 2.24$ :

       cửa sổ: {C, D}     đường quét tại x=3
 4 | . . . . . .          (A, B đã rời cửa sổ)
 3 | . . . D<-- đang xét
 2 | . . . . . .
 1 | . . C . . .  <-- chỉ còn C trong dải y∈[3-d, 3+d]
 0 | . . . . . .

Kết quả: cặp gần nhất là (A,C) và (C,D), cùng khoảng cách $\approx 2.236$ .

Cài đặt

Sweep line — $O (N \log N)$

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

struct Point { long long x, y; };

double dist(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);   // dùng double cho căn bậc hai
}

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;                       // quét theo x tăng dần
    });

    double d = 1e18;
    set<pair<long long,long long>> active;      // cửa sổ hoạt động, khoá = {y, x}

    int left = 0;
    for (int i = 0; i < n; i++) {
        // Loại các điểm có x cách x_i ít nhất d: không thể tạo cặp tốt hơn d
        while (left < i && pts[i].x - pts[left].x >= d) {
            active.erase({pts[left].y, pts[left].x});
            left++;
        }
        // Chỉ duyệt các điểm có y trong [y_i - d, y_i + d]
        long long lo = (long long)floor(pts[i].y - d);
        auto it = active.lower_bound({lo, LLONG_MIN});
        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;
}

Chia để trị — $O (N \log N)$

double closest_rec(vector<Point>& p, int l, int r) {
    if (r - l <= 3) {                            // đáy: ít điểm, xét vét cạn
        double d = 1e18;
        for (int i = l; i < r; i++)
            for (int j = i+1; j < r; j++)
                d = min(d, dist(p[i], p[j]));
        sort(p.begin()+l, p.begin()+r,
             [](const Point&a, const Point&b){ return a.y < b.y; });
        return d;
    }
    int mid = (l + r) / 2;
    long long mx = p[mid].x;                      // hoành độ đường chia
    double d = min(closest_rec(p, l, mid), closest_rec(p, mid, r));

    // Hợp hai nửa đã sắp theo y -> đoạn [l,r) sắp theo y, mất O(r-l)
    inplace_merge(p.begin()+l, p.begin()+mid, p.begin()+r,
                  [](const Point&a, const Point&b){ return a.y < b.y; });

    // Lấy các điểm trong dải rộng 2d quanh đường chia
    vector<Point> strip;
    for (int i = l; i < r; i++)
        if (llabs(p[i].x - mx) < d) strip.push_back(p[i]);

    // Trong dải, mỗi điểm chỉ so với các điểm sau có y cách dưới d (tối đa ~7)
    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(),
         [](const Point&a, const Point&b){ return a.x < b.x; });
    return closest_rec(pts, 0, pts.size());
}

Độ phức tạp

Sweep line. Mỗi điểm được chèn và xoá khỏi set đúng một lần, mỗi thao tác $O (\log N)$ . Khi xét điểm $i$ , số điểm trong dải $[y_{i} - d, y_{i} + d]$ của cửa sổ là hằng (lập luận hình chữ nhật: không quá $~ 8$ điểm đôi một cách nhau $\geq d$ trong vùng $2 d \times d$ ), nên vòng while quét set chạy $O (\log N)$ mỗi điểm. Tổng: $O (N \log N)$ thời gian, $O (N)$ bộ nhớ cho set.

Chia để trị. Quan hệ đệ quy $T (N) = 2 T (N / 2) + O (N)$ : phần $O (N)$ gồm inplace_merge để giữ thứ tự theo $y$ và quét dải. Vì mỗi điểm trong dải chỉ so với $O (1)$ điểm kế tiếp, bước gộp là tuyến tính. Theo định lý thợ, $T (N) = O (N \log N)$ , bộ nhớ $O (N)$ (đệ quy + mảng strip).

⚠️ Lỗi thường gặp

Tràn số khi tính bình phương khoảng cách. Với $| x |, | y | \leq 10^{9}$ , đại lượng $d x^{2} + d y^{2}$ có thể tới $\approx 8 \cdot 10^{18}$ — vẫn nằm trong long long nhưng tràn int ngay. Lưu tọa độ bằng long long; nếu muốn so sánh không cần căn, hãy so bình phương khoảng cách (kiểu long long) thay vì double, tránh sai số dấu phẩy động.
Quên cập nhật/thu hẹp cửa sổ trong sweep line. Nếu không đẩy các điểm có $x_{i} - x \geq d$ ra khỏi set, độ phức tạp tụt về $O (N^{2})$ (mỗi bước quét cả set). Vòng while (pts[i].x - pts[left].x >= d) là bắt buộc, và phải dùng giá trị $d$ hiện tại (đang giảm dần) chứ không phải hằng cố định.
Dùng >= thay vì < (hoặc ngược lại) ở biên dải. Điều kiện cửa sổ và điều kiện dải phải nhất quán với cách bạn định nghĩa "tốt hơn". Sai biên một dấu bằng có thể bỏ sót đúng cặp tối ưu khi hai điểm cách nhau đúng $d$ . Khi nghi ngờ, nới biên thành $\leq$ cho an toàn (vẫn $O (N \log N)$ ).
Chia để trị: quên giữ mảng sắp theo $y$ sau đệ quy. Trick $O (N \log N)$ dựa vào việc sau mỗi lần closest_rec, đoạn đó đã được sắp theo $y$ để gộp tuyến tính. Nếu mỗi tầng lại sort theo $y$ từ đầu, chi phí thành $O (N \log^{2} N)$ . Dùng inplace_merge (hoặc tự merge) thay cho sort.
Trường hợp biên: $N < 2$ hoặc các điểm trùng nhau. Với $N \leq 1$ không tồn tại cặp — cần xử lý riêng (thường trả $+ \infty$ hoặc báo lỗi). Khi có hai điểm trùng tọa độ, $d = 0$ ; code phải chấp nhận $d = 0$ và không chia cho $d$ ở bất kỳ đâu.
So sánh double để xuất kết quả. Nếu đề yêu cầu in khoảng cách, in double với đủ chữ số (printf("%.6f")); nếu đề yêu cầu bình phương khoảng cách nguyên, hãy giữ toàn bộ phép tính trong long long và không đụng tới sqrt.

Biến thể / Mở rộng

Phiên bản 1D (trên đường thẳng): sắp các điểm theo tọa độ rồi đáp án là khoảng cách nhỏ nhất giữa hai phần tử kề nhau — chỉ cần một lượt $O (N \log N)$ (do sắp xếp). Đây là nền tảng trực giác của bài 2D; bài cowline bên dưới luyện đúng dạng cửa sổ trượt theo tọa độ này.
Khoảng cách Manhattan / Chebyshev: đổi hệ tọa độ ( $u = x + y, v = x - y$ ) biến Manhattan thành Chebyshev, rồi quét tương tự.
k cặp gần nhất / k láng giềng gần nhất: mở rộng bằng cây k-d (k-d tree) hoặc lưới băm (grid hashing) với kích thước ô $\approx d$ .

Bài tập luyện

Đoạn Liên Tiếp Ngắn Nhất (cowline) — (Trung cấp) Phiên bản 1D của closest pair: sắp các điểm theo tọa độ rồi trượt cửa sổ tìm đoạn ngắn nhất — luyện đúng ý tưởng "sort + cửa sổ trượt theo tọa độ" làm nền cho sweep line 2D.
Chứng Cứ Ngoại Phạm (cowlibi) — (Trung cấp) Với mỗi con bò chỉ cần kiểm tra vài sự kiện gần nhất theo thời gian sau khi sắp xếp — đúng tinh thần "sau khi sort, mỗi điểm chỉ so với một số hằng láng giềng" của thuật toán closest pair.

Ghi chú: pool CTOJ hiện chưa có bài "cặp điểm gần nhất" 2D thuần (chia để trị / dải giữa) đúng nhãn. Hai bài trên là những bài sát kỹ thuật nhất hiện có (sắp xếp + cửa sổ/láng giềng gần nhất). Sẽ bổ sung thang dễ→khó khi pool có thêm bài đúng chủ đề.