Tìm khoảng cách cặp điểm gần nhau nhất bằng C++ (closest pair of points)

 

Thuật toán:

- Đầu tiên ta sắp xếp các điểm theo x để có thể dùng thuật toán chia để trị

- Gọi f(l, r) là hàm trả về khoảng cách cặp điểm gần nhau nhất từ l đến r, hàm f được triển khai như sau:

TH1 (l=r): Nếu chỉ có 1 điểm ta trả về +oo 

TH2 (l=r-1): Nếu có 2 điểm ta trả về khoảng cách của 2 điểm đó 

TH3: Gọi d là kết quả khoảng cách cặp điểm gần nhau nhất

+Nhiều hơn 2 điểm ta chia các điểm trong l -> r thành 2 tập hợp ngăn cách bời mid=(l+r)/2, áp dụng chia để trị lấy kết quả d=min(f(l, mid), f(mid+1, r). 

+Tuy nhiên d chưa phải là khoảng cách cặp điểm nhau gần nhất trong đoạn (l ->r) vì ta còn chưa tính khoảng các điểm từ tập 1 sang tập 2 qua mid (tập 3).

+ Khoảng cách cặp điểm nhau gần nhất trong tập thứ 3 chúng ta chỉ cần tính là các điểm trong đoạn (mid - d, mid + d) vì nếu các điểm ở ngoài đoạn này thì sẽ có khoảng cách lớn hơn d cho nên loại

+ Đối với tập thứ 3 chúng ta cần sắp xếp các điểm theo Y trước (ý đồ của sắp xếp này là để giảm O(n^2) xuống O(n) khi duyệt 2 for tìm khoảng cách cặp điểm gần nhau nhất), for i,j .. if.. d=min(d, distance(a[i], a[j]).
=> Cuối cùng trả về f(l,r) = d

Note:

- Độ phức tạp của thuật toán trên O(n(logn)^2)= (logn của chia để trị)*(nlogn sắp xếp) 

- Hai vòng for mà có độ phức tạp O(n) là do trong lúc lặp đã có loại bỏ trường hợp j.Y - i.Y > d (vì j.Y tiếp tục tăng khiến j.Y - i.Y tiếp tục tăng > d nên ta kết thúc ko lặp nữa) 

- Để giảm độ phức tạp xuống còn O(nlogn) chúng ta sẽ giảm thời gian sắp xếp xuống còn O(n) bằng cách swap 2 điểm (nếu Y điểm 1 lớn hơn, trong trường hợp l=r-1) và kết hợp trọn 2 tập (l, mid) và (mid+1, r) theo Y trong lúc chia đệ trị.

- Code đã được kiểm tra trên spoj vn

Code: O(nlogn)

#include<bits/stdc++.h>

#define MAXN 1000111

#define oo 1000111000

using namespace std;

struct point {

    double x, y;

};

point a[MAXN], t[MAXN];

bool cmp_x(point a, point b) {

    return a.x < b.x;

}

bool cmp_y(point a, point b) {

    return a.y < b.y;

}

double dis(point a, point b) {

    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));

}

double f(int l, int r) {

    if (r <= l) return oo;

    if (r == l + 1) {

        if (!cmp_y(a[l], a[r])) swap(a[l], a[r]);

        return dis(a[l], a[r]);

    }

    int m = (l + r) / 2;

    double xMid= a[m].x;                    //declare xMid because a[m].x will be changed by sorting follow y

    double d= min(f(l, m), f(m+1, r));

    merge(a+l, a+m+1, a+m+1, a+r+1, t, cmp_y);

    copy(t, t+r-l+1, a+l);                      //had sort a follow y

    vector<point> v;

    for (int i=l; i<=r; i++)

        if (abs(a[i].x - xMid) < d) v.push_back(a[i]);

       

    for (int i = 0; i < v.size(); ++i)

    for (int j = i+1; j < v.size() && (v[j].y - v[i].y) < d; ++j)

        d= min(d, dis(v[i], v[j]));            

   

    return d;

}

int main() {

   

    int n; cin >> n;

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

    sort(a+1, a+n+1, cmp_x);

   

    cout << fixed << setprecision(3) << f(1, n);

   

}

Link tham khảo thêm:

O(n(logn)^2): https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
O(nlogn): https://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/