Submission #1354703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354703		marcus06	Mobile (BOI12_mobile)	C++20	0 / 100	617 ms	12184 KiB

mobile

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

void solve() {
    int N, L;
    cin >> N >> L;
    vector <int> x(N), y(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
    }

    vector <int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return x[i] < x[j];
    });

    auto possible = [&](double d) -> bool {
        vector <pair <double, double>> range;
        for (int i: ord) {
            if (y[i] >= d) return true;
            double p = y[i];
            double delta = sqrt(d * d - p * p);

            double l = (double) x[i] - delta, r = (double) x[i] + delta;
            while (!range.empty() && range.back().second >= l) {
                l = min(l, range.back().first);
                r = max(r, range.back().second);
                range.pop_back();
            }
            range.emplace_back(l, r);
        }
        for (auto [x, y]: range) {
            if (x <= 0 && y >= L) return false;
        }
        return true;
    };

    double l = 0, r = L;
    for (int iter = 0; iter < 64; ++iter) {
        double mid = (l + r) / 2; //check if there exist a point which distance >= mid
        if (possible(mid))
            l = mid;
        else
            r = mid;
    }
    cout << setprecision(20) << fixed;
    cout << l << '\n';
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif

    int tt = 1;
    while (tt--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
    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