Submission #1270274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270274		os_bein_laggin	Mobile (BOI12_mobile)	C++20	0 / 100	276 ms	16016 KiB

mobile

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

struct Interval {
    double l, r;
};

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

    int N;
    long long L;
    cin >> N >> L;

    vector<pair<long long, long long> > stations(N);
    for (int i = 0; i < N; i++) {
        cin >> stations[i].first >> stations[i].second;
    }

    auto canCover = [&](double R) -> bool {
        double covered = 0.0;

        for (int i = 0; i < N && covered < L; i++) {
            long long x = stations[i].first;
            long long y = stations[i].second;

            if (1.0 * y * y > R * R) continue; // cannot touch highway

            double dx = sqrt(R * R - 1.0 * y * y);
            double left = max(0.0, (double)x - dx);
            double right = min((double)L, (double)x + dx);

            if (left > covered + 1e-9) return false; // gap
            covered = max(covered, right);
        }

        return covered >= L;
    };

    double lo = 0.0, hi = 2e9; // upper bound big enough
    for (int it = 0; it < 60; it++) { // binary search precision
        double mid = (lo + hi) / 2.0;
        if (canCover(mid)) hi = mid;
        else lo = mid;
    }

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

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