本地AC,提交WA?求助求助
查看原帖
本地AC,提交WA?求助求助
392696
Roshin楼主2022/3/13 01:14

本地输出240.5560(是正确答案),在其他电脑上答案却不一样。感觉也不是数组初始化的问题,我的电脑是macbook m1,洛谷各种编译选项都试过了,还是90分,过不去第六个点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#define pb push_back
#define x first
#define y second
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 1e4 + 10;
const double eps = 1e-6;
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef std::pair<double, double> PDD;
int n;
double min_d;
PDD a[N];

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

double dfs(int l, int r){
    if(l >= r) return min_d;
    int mid = (l + r) >> 1;
    double ans = min(dfs(l, mid), dfs(mid + 1, r));
    double midx = a[mid].x;
    int i = l, j = mid + 1, cnt = 0;
    vector<PDD> tmp;
    while(i <= mid && j <= r){
        if(a[i].y < a[j].y) tmp.pb(a[i++]);
        else tmp.pb(a[j++]);
    }

    while(i <= mid) tmp.pb(a[i++]);
    while(j <= r) tmp.pb(a[j++]);
    for(int i = l; i <= r; i++)
        a[i] = tmp[i - l];
    tmp.clear();
    cnt = 0;
    for(int i = l; i <= r; i++){
        if(a[i].x >= midx - ans && a[i].x <= midx + ans)
            tmp.pb(a[i]);
    }
    for(int i = 0; i < tmp.size(); i++)
        for(int j = i - 1; j >= 0 && tmp[i].y - tmp[j].y + eps <= ans; j--)
            ans = min(ans, get(tmp[i], tmp[j]));
    min_d = min(min_d, ans);
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        double x, y;
        scanf("%lf%lf", &x, &y);
        a[i] = {x, y};
    }
    min_d = get(a[0], a[n - 1]);
    sort(a, a + n);
    double ans = dfs(0, n);
    printf("%.4lf", ans);
    return 0;
}

2022/3/13 01:14
加载中...