제출 #1324507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324507		jack205	Mobile (BOI12_mobile)	C++20	100 / 100	596 ms	31620 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
long long n, l;
pair<double,double> a[MAXN+5];
const double eps = 1e-12;

struct Seg { double L, R; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> l;
    for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;

    vector<Seg> stk;
    stk.reserve(n);

    auto ok = [&](double mid)->bool {
        stk.clear();
        double r2 = mid * mid;

        for (int i = 1; i <= n; i++) {
            double x = a[i].first, y = a[i].second;
            double yy = y * y;
            if (r2 < yy) continue;

            double dx = sqrt(max(0.0, r2 - yy));
            double L = x - dx, R = x + dx;

            while (!stk.empty() && stk.back().L >= L - eps) stk.pop_back();
            stk.push_back({L, R});
        }

        double cur = 0;
        for (auto &s : stk) {
            if (s.L > cur + eps) return false;
            cur = max(cur, s.R);
            if (cur >= l - eps) return true;
        }
        return cur >= l - eps;
    };

    double st = 0, ed = 1e12 + 5, ans = -1;
    for(int it=0; it<60; it++){
        double mid = (st + ed) / 2;
        if (ok(mid)) ans = ed = mid;
        else st = mid;
    }

    cout << fixed << setprecision(6) << ans << "\n";
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5