最后一个点过不去
查看原帖
最后一个点过不去
1263886
KoviOfficial楼主2025/1/11 22:47

求助

为什么最后一个测试点过不了啊

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Point {
    double x, y;
    int id;
};

int ret_1 = 0, ret_2 = 0;
double ans = (double)__INT64_MAX__;

Point p[200001];
int tmp[2000];

double distance(const Point& a, const Point& b) {
    return pow(pow(a.x - b.x, 2) + pow(a.y - b.y, 2), 0.5);
}

void Update(int id_1, int id_2, double dis) {
    if (id_1 > id_2) swap(id_1, id_2);
    if (dis == ans) {
        if (ret_1 > id_1 || ret_1 == id_1 && ret_2 > id_2) {
            ret_1 = id_1, ret_2 = id_2;
        }
    }
    else {
        ret_1 = id_1, ret_2 = id_2, ans = dis;
    }
}


int cmpPoint(Point& a, Point& b) {
    return a.x <  b.x;
}

int cmpArr(int x, int y) {
    return p[x].x < p[y].x;
}


void findClosest(int left, int right) {
    if (left == right) {
        return;
    }
    if (left + 1 == right) {
        auto cur = distance(p[left], p[right]);
        if (ans > cur) {
            Update(p[left].id, p[right].id, cur);
            return;
        }
    }
    int mid = (left + right) >> 1;
    findClosest(left, mid);
    findClosest(mid + 1, right);
    int k = 0;
    for (int i = left; i <= right; ++i) {
        if (fabs(p[mid].x - p[i].x) <= ans) {
            tmp[k++] = i;
        }
    }
    sort(tmp, tmp + k, cmpArr);
    for (int i = 0; i < k; ++i) {
        for (int j = i + 1; j < k && p[tmp[j]].y - p[tmp[i]].y <= ans; ++j) {
            if (ans > distance(p[tmp[i]], p[tmp[j]])) {
                Update(p[tmp[i]].id, p[tmp[j]].id, distance(p[tmp[i]], p[tmp[j]]));
            }
        }
    }
}


signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }
    sort(p, p + n, cmpPoint);
    findClosest(0, n - 1);
    printf("%.4lf\n", ans);
    return 0;
}
2025/1/11 22:47
加载中...