Submission #1247196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247196		tkhoi13	Mobile (BOI12_mobile)	C++20	0 / 100	1096 ms	56008 KiB

mobile

#include <bits/stdc++.h>
#define db double
#define all(x) begin(x), end(x)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
using namespace std;

int n;
db l;
vector<pair<db, db>> cord;

bool ok(db x) {
    vector<pair<db, db>> cutted;
    for (auto &[x0, y0] : cord) {
        if (y0 > x) continue;
        db t = sqrt(x * x - y0 * y0);
        db l0 = max(0.0, x0 - t);
        db r0 = min(l, x0 + t);
        if (l0 > r0) continue;
        cutted.emplace_back(l0, r0);
    }

    if (cutted.empty()) return false;

    sort(all(cutted));
    db covered = 0;
    for (auto &[l0, r0] : cutted) {
        if (l0 > covered + 1e-9) return false;
        covered = max(covered, r0);
        if (covered >= l - 1e-9) return true;
    }

    return false;
}

void solve() {
    cin >> n >> l;
    vector<pair<int, int>> all;
    REP(i, n) {
        int x, y;
        cin >> x >> y;
        all.emplace_back(x, y);
    }

    sort(all.begin(), all.end());
    for (auto &[x, y] : all)
        if (cord.empty() || cord.back().first != x)
            cord.emplace_back(x, y);
    n = cord.size();

    db lo = 0, hi = 1e9 * sqrt(2);
    REP(_, 50) {
        db mid = (lo + hi) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid;
    }

    cout << fixed << setprecision(6) << hi << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}

• 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