数据有点水啊我这都能过....?

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

Sandmonth @ 2021-04-07 17:40:27


pair<ll, ll> a[N];
double ans = inf;
double get(ll ls, ll rs){
    double lt = abs(a[ls].first - a[rs].first) * abs(a[ls].first - a[rs].first);
    double rt = abs(a[ls].second - a[rs].second) * abs(a[ls].second - a[rs].second);
    return sqrt(1.0 * lt + rt);
}
ll dfs(ll l, ll r){
    if(l == r) return l;
    ll mid = (l + r) >> 1;
    double ls = dfs(l, mid) , rs = dfs(mid + 1, r);
//    cout << ls << ' ' << rs << endl;
    double res = inf;
    for(ll i = ls; i <= rs; i ++){
        res = min(res, get(i, i - 1));
        res = min(res, get(i, i - 2));
    }
    ans = min(ans, get(ls, rs));
    ans = min(ans , res);
    return mid;
}
int main(){
    ll n;
    RLL(n);
    FOR(i, 1, n){
        RLL2(a[i].first, a[i].second);
    }
    sort(a + 1, a + 1 + n);
    dfs(1, n);
    printf("%.4f", ans);
    return 0;
}

|