113分qwq,求助

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

Fire_Raku @ 2023-08-20 08:48:14

一直找不出来错,其他的点 WA 了,我觉得可能就是小细节了,找不到QWQ

#include <bits/stdc++.h>
using namespace std;
long long read(){
    long long x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c - '0');
        c = getchar();
    }
    return x * f;
}
long long n;
int tmp[400010];
struct node{
    long long x, y;
}a[400010], c[400010];
bool cmp1(node a, node b){
    return a.x < b.x;
}
long long dist(int i, int j){
    return (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
}
long long qsort(int l, int r){
    long long d = 1ll << 62;
    if(l == r) return d;
    int mid = (l + r) >> 1, k = 0, lx = l, rx = mid + 1, tot = l;
    long long lmin = qsort(l, mid), rmin = qsort(mid + 1, r);
    d = min(lmin, rmin);
    while(lx <= mid && rx <= r){
        if(a[lx].y <= a[rx].y){
            c[tot++] = a[lx++];
        }
        else c[tot++] = a[rx++];
    }
    while(lx <= mid) c[tot++] = a[lx++];
    while(rx <= r) c[tot++] = a[rx++];
    for(int i = l; i <= r; i++) a[i] = c[i];
    long long dd = d;
    dd = sqrt(d);
    for(int i = l; i <= r; i++){
        if(fabs(a[mid].x - a[i].x) <= dd){
            tmp[++k] = i;
        }
    }
    for(int i = 1; i <= k; i++){
        for(int j = i + 1; j <= k && a[tmp[j]].y - a[tmp[i]].y <= dd; j++){
            d = min(d, dist(tmp[i], tmp[j]));
            dd = sqrt(d);
        }
    }
    return d;
}
int main(){
    n = read();
    for(int i = 1; i <= n; i++){
        a[i].x = read(), a[i].y = read();
    }
    sort(a + 1, a + n + 1, cmp1);
    cout << qsort(1, n) << endl;
    return 0;
}

by Fire_Raku @ 2023-08-20 09:13:44

找到了,a[mid].x 要在排序前保存下来


by Elma_ @ 2023-08-20 19:36:04

代码要自己调.jpg


by jr_linys @ 2023-09-20 11:35:03

@Fire_Raku 来自一个月后的感谢


by liuyinuo2 @ 2024-11-25 18:40:05

@Fire_Raku来自一年后的感谢


|