Submission #1132524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132524		vedeshray	Mobile (BOI12_mobile)	C++20	100 / 100	274 ms	15944 KiB

mobile

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

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

    ll n, l; cin >> n >> l;
    vector<pair<ll, ll>> stations(n);
    for (auto &[x, y] : stations) {cin >> x >> y;}
    double minRad = 0, maxRad = 2e9; // maxRad has to be enough to reach the ends of the highway
    while (minRad < maxRad - 1e-3) { // we have a 1e-3 (.001) leeway on the answer
        double midRad = (minRad + maxRad) / 2;
        double currPoint = 0; // current uncovered point on the highway
        for (auto [x, y] : stations) {
            double b = sqrt(midRad * midRad - y * y); // b = dist from the x coord of the station to the bound of the station's circle intersection on the highway.
            double segLeft = x - b, segRight = x + b;
            if (segLeft <= currPoint) {currPoint = max(currPoint, segRight);}
        }
        if (currPoint >= l) {maxRad = midRad;} // if all the highway has been covered
        else {minRad = midRad;} // means a point was far away enough to not be covered
    }
    cout << fixed << setprecision(6) << minRad << '\n';
}

• 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