WA两个, 求助, 感谢

P1429 平面最近点对(加强版)

mushezi @ 2023-03-28 13:18:29

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

const int N = 2e5 + 5;

struct point{
    double x, y;
} a[N], b[N];

bool cmpx(point & a, point & b){
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

double dist(point & a, point & b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double solve(int l, int r){
    if(l == r) return 2e9;
    int mid = (l + r) >> 1;
    double d = min(solve(l, mid), solve(mid + 1, r));
    point cur = a[mid];

    {
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(a[i].y < a[j].y) b[++k] = a[i++];
            else b[++k] = a[j++]; 
        }
        while(i <= mid) b[++k] = a[i++];
        while(j <= r) b[++k] = a[j++];

        for(int t = l; t <= r; t++){
            a[t] = b[t - l + 1];
        }
    }

    int k = 0;
    for(int i = l; i <= r; i++){
        if(abs(a[i].x - cur.x) < d) b[++k] = a[i];
    }

    for(int i = 1; i < k; i++){
        for(int j = i + 1; j <= k && abs(b[j].y - b[i].y) < d; j++){
            d = min(d, dist(b[i], b[j]));
        }
    }

    return d;
}

int n;
double x, y;

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

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

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

    cout << fixed << setprecision(4) << solve(1, n);

    return 0;
}

|