Bài toán

Cho N điểm trên mặt phẳng tọa độ, cần tìm 2 điểm sao cho khoảng cách giữa chúng là nhỏ nhất.

Khoảng cách giữa 2 điểm được tính bằng công thức: \(d(p_i, p_j) = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\)

Bài viết này sẽ trình bày thuật toán chia để trị để tìm cặp điểm gần nhất trong \(O(N\log N)\)

Thuật toán

Áp dụng tư tưởng chia để trị:

Chia N điểm cần xử lý thành 2 tập hợp bằng một đường thẳng đứng
Gọi đệ quy tìm cặp điểm gần nhất cho tập bên trái và tập bên phải
Tìm khoảng cách ngắn nhất giữa một điểm thuộc tập bên trái và một điểm thuộc tập bên phải.

Bước 3 là bước khó nhất trong các bước trên.

Giả sử trong bước 1 ta chia N điểm thành 2 tập bằng đường thẳng có phương trình \(x = a\), và trong bước 2, sau khi gọi đệ quy có được khoảng cách giữa cặp điểm gần nhất là \(D\). Một cách tự nhiên, ta thấy trong bước 3 chỉ cần xét những điểm có \(\mid x_i - a \mid < D\) vì các điểm bên ngoài khoảng đó chắc chắn sẽ cho khoảng cách lớn hơn \(D\).

Ngoài ra, với mỗi điểm \(p_i\) thỏa điều kiện ở trên, ta chỉ cần so nó với những điểm \(p_j\) cũng thỏa điều kiện ở trên và \(p_j\) có \(y_i - D < y_j \leq y_i\) (*).

Để thực hiện nhanh bước 1 ta cần sắp xếp các điểm theo \(x\), còn bước 3 cần phải sắp các điểm theo \(y\). Để giải quyết vấn đề này, ta sắp các điểm theo \(x\) ngay từ đầu, rồi lồng việc sắp xếp theo \(y\) vào đệ quy bằng sắp xếp trộn.

Thoạt nhìn thì phương pháp này không có độ phức tạp \(O(N\log N)\), tuy nhiên có thể chứng minh được độ phức tạp là \(O(N\log N)\) do bước 3 có độ phức tạp \(O(N)\) (số điểm thỏa điều kiện (*) của mỗi điểm là hằng số, không phụ thuộc vào N).

Cài đặt

Code sau được dùng để nộp cho bài NEAREST

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
    double x, y;
};

bool cmp_x(const point &a, const point &b) {
    return a.x < b.x;
}

bool cmp_y(const point &a, const point &b) {
    return a.y < b.y;
}

#define MAXN 100000
point a[MAXN];
double mindist; // biến lưu kết quả bài toán

// tính khoảng cách giữa a và b rồi update kết quả
void upd_ans(const point &a, const point &b) {
    double dist = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    if (dist < mindist) mindist = dist;
}

void find(int l, int r) {
    if (r <= l) return;
    // đoạn [l,r] có 2 phần tử
    if (r == l + 1) {
        upd_ans(a[l], a[r]);
        // sắp các phần tử lại theo y
        if (!cmp_y(a[l], a[r])) swap(a[l], a[r]);
        return;
    }

    int m = (l + r) / 2;
    double midx = a[m].x;
    find(l, m);
    find(m+1, r);

    static point t[MAXN];
    // trộn a[l,m] và a[m+1,r] lại, lưu vào mảng tạm t
    merge(a+l, a+m+1, a+m+1, a+r+1, t, cmp_y);
    // copy từ t về lại a
    copy(t, t+r-l+1, a+l);

    // mảng t ở đây lưu các phần tử thỏa |x_i - midx| < mindist,
    // với số lượng phần tử là tm
    // do đã sort nên các phần tử sẽ có y tăng dần
    int tm = 0;
    for (int i=l; i<=r; i++) if (abs(a[i].x-midx) < mindist) {
        for (int j=tm-1; j>=0 && t[j].y > a[i].y-mindist; j--)
            upd_ans(a[i], t[j]);
        t[tm++] = a[i];
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    for (int i=0; i<n; i++) cin >> a[i].x >> a[i].y;

    mindist = 1E20;
    sort(a, a+n, cmp_x);
    find(0, n-1);

    printf("%.3lf", mindist);
    return 0;
}