Submission #1083687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083687		vjudge1	Mobile (BOI12_mobile)	C++17	95 / 100	1004 ms	35420 KiB

mobile

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

using namespace std;

// Function to check if all points on the highway [0, L] can be covered with distance R
bool canCoverAllPoints(const vector<pair<double, double>>& stations, double R, double L) {
    double currentCoverage = 0.0;
    
    for (const auto& station : stations) {
        double xi = station.first;
        double yi = station.second;
        
        if (yi > R) continue; // This base station cannot help at this R
        
        double reach = sqrt(R * R - yi * yi);
        double startCoverage = max(0.0, xi - reach);
        double endCoverage = xi + reach;
        
        // Extend coverage if this base station helps
        if (startCoverage <= currentCoverage) {
            currentCoverage = max(currentCoverage, endCoverage);
        }
        
        if (currentCoverage >= L) return true;
    }
    
    return currentCoverage >= 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;
}

• 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: 0 / 5