「学习笔记」杂项算法大礼包

青旅半醒 2023-08-17 17:31 143阅读 0赞

平面最近点对。

#include <algorithm>
    #include <cstdio>
    #include <vector>
    #include <cmath>
    using namespace std;
    
    #define fs first
    #define sc second
    
    typedef double db;
    typedef pair<db, db> pa;
    
    const int N = 2e5 + 10;
    const db EPS = 1e-10;
    
    int cmp1(pa a, pa b) { return a.fs - b.fs < -EPS; }
    int cmp2(pa a, pa b) { return a.sc - b.sc < -EPS; }
    int n, m;
    pa a[N], arr[N];
    
    db p(db x) { return x * x; }
    db d(pa x, pa y) { return sqrt(p(x.fs - y.fs) + p(x.sc - y.sc)); }
    
    db divide(int l, int r) {
        if(r - l <= 2) {
            db ans = 3e18;
            for(int i = l; i < r; i ++)
                for(int j = i + 1; j <= r; j ++)
                    ans = min(ans, d(a[i], a[j]));
            sort(a + l, a + r + 1, cmp2);
            return ans;
        }
        int mid = (l + r) >> 1, p1 = l, p2 = mid + 1;
        db Mid = a[mid].fs, ans = min(divide(l, mid), divide(mid + 1, r));
        for(int i = l; i <= r; i ++) {
            if(p2 > r || (p1 <= mid && a[p1].sc - a[p2].sc < -EPS)) arr[i] = a[p1 ++];
            else arr[i] = a[p2 ++];
        }
        m = 0;
        for(int i = l; i <= r; i ++) a[i] = arr[i];
        for(int i = l; i <= r; i ++) if(fabs(a[i].fs - Mid) <= ans) arr[++ m] = a[i];
        for(int i = 1; i <= m; i ++)
            for(int j = i + 1; j <= i + 7 && j <= m; j ++) {
                db dis = d(arr[i], arr[j]);
                ans = min(ans, dis);
            }
        return ans;
    }
    
    int main() {
        while(~ scanf("%d", &n)) {
            for(int i = 1; i <= n; i ++)
                scanf("%lf%lf", &a[i].fs, &a[i].sc);
            sort(a + 1, a + n + 1, cmp1);
            printf("%.4lf\n", divide(1, n));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11385391.html