好哥哥们,思路应该是对的。为啥会tle啊

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

Myzc @ 2023-03-07 13:42:55


#include <bits/stdc++.h>

const int N = 2e5 + 5;
struct Node{
    Node(long long x, long long y): x(x), y(y) {}
    Node() {}
    long long x;
    long long y;

    bool operator < (const Node &t) const{
        if(x == t.x) {
            return x < t.x;
        }
        return x < t.x;
    }
}node[N];
int n;
int temp[N];

bool cmpy(const int &n1,const int &n2) {
    return node[n1].y < node[n2].y;
}

long long dis(const Node &n1,const Node &n2) {
    return (n1.x - n2 .x) * (n1.x - n2.x) +
        (n1.y - n2.y) * (n1.y - n2.y);
}

long long cal(int l, int r) {
    //std::cout << "l = " << l << ' ' << "r = " << r << '\n'; 
    if(l >= r) {
        return 0x3f3f3f3f3f3f3f3f;
    } else if(l + 1 == r) {
        return dis(node[l], node[r]);
    }

    int mid = (l + r) >> 1;
    long long lDis = cal(l, mid);
    long long rDis = cal(mid + 1, r);

    long long d = std::min(lDis, rDis);
    //std::cout << l << ' ' << r << ' ' << d << '\n';

    int sz = 0;
    for(int i = l; i <= r; i++){
        if(fabs(node[mid].x - node[i].x) < d) {
            temp[sz++] = i;
        }
    }

    std::sort(temp, temp + sz, cmpy);
    long long d1 = d;

    for(int i = 0; i < sz; i++) {
        for(int j = i + 1; j < sz && node[temp[j]].y - node[temp[i]].y < d; j++) { 
            d1 = std::min(d1, dis(node[temp[i]], node[temp[j]]));
        }
    }

    return d1;
}

int main() {
    std::cin >> n;

    for(int i = 0; i < n; i++) {
        scanf("%d %d", &node[i].x, &node[i].y);
    }

    std::sort(node, node + n);
    long long ans = cal(0, n - 1);

    printf("%.4lf\n", sqrt(ans) );

    return 0;
}

|