最后一个点过不去,求调
查看原帖
最后一个点过不去,求调
989175
ZSHZSH_楼主2025/6/15 11:38
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int tmp[200001];
struct coor {
    int x;
    int y;
}Arr[200001];
int n;
bool cmp(coor& A, coor& B) {
    if (A.x != B.x) {
        return A.x < B.x;
    }
    else {
        return A.y < B.y;
    }
}
double distance(coor A, coor B) {
    return sqrt(pow(B.x - A.x, 2) + pow(B.y - A.y, 2));
}
double f(int L,int R) {
    if (L==R)
    {
        return 2<<20;
    }
    else if(L+1==R)
    {
        return distance(Arr[L], Arr[R]);
    }
    else {
        int mid = (L + R) / 2;
        int midx = Arr[mid].x;
        double ans = min(f(L, mid), f(mid + 1, R));

        int cnt = 0;
        for (int i = L; i<=R; i++) {
            if (abs(Arr[i].x - midx) < ans) {
                tmp[cnt++] = i;
            }
        }
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt && Arr[tmp[j]].y - Arr[tmp[i]].y < ans; j++) {
                double t = distance(Arr[tmp[i]], Arr[tmp[j]]);
                if (t < ans) {
                    ans = t;
                }
            }
        }
        return ans;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> Arr[i].x;
        cin >> Arr[i].y;
    }
    sort(Arr, Arr + n, cmp);
    printf("%.4f", f(0, n-1));
    return 0;
}
2025/6/15 11:38
加载中...