Submission #1083685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083685		vjudge1	Mobile (BOI12_mobile)	C++17	0 / 100	590 ms	32404 KiB

mobile

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

// Function to check if a given radius R can cover the entire highway
bool canCoverAllPoints(const vector<pair<double, double>>& stations, double R, double L) {
    double coveredUntil = 0.0;

    for (const auto& station : stations) {
        double xi = station.first;
        double yi = station.second;

        if (yi > R) continue; // This base station is too far away to help

        // Calculate the maximum x-range this station can cover
        double d = sqrt(R * R - yi * yi);
        double coverageStart = max(0.0, xi - d);
        double coverageEnd = xi + d;

        // Extend the coverage
        coveredUntil = max(coveredUntil, coverageEnd);

        if (coveredUntil >= L) return true; // Covered the entire highway
    }

    return coveredUntil >= L;
}

int main() {
    int N;
    double L;
    cin >> N >> L;

    vector<pair<double, double>> stations(N);
    for (int i = 0; i < N; ++i) {
        double xi, yi;
        cin >> xi >> yi;
        stations[i] = {xi, yi};
    }

    // Binary search for the smallest possible R
    double low = 0.0;
    double high = 1e9;
    double epsilon = 1e-4; // Precision to ensure accuracy within 1e-3

    while (high - low > epsilon) {
        double mid = (low + high) / 2.0;
        if (canCoverAllPoints(stations, mid, L)) {
            high = mid; // Try smaller radius
        } else {
            low = mid; // Increase radius
        }
    }

    cout << fixed << setprecision(6) << high << endl;
    return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'bool canCoverAllPoints(const std::vector<std::pair<double, double> >&, double, double)':
mobile.cpp:20:16: warning: unused variable 'coverageStart' [-Wunused-variable]
   20 |         double coverageStart = max(0.0, xi - d);
      |                ^~~~~~~~~~~~~

• 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