제출 #1286667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286667		samarthkulkarni	Mobile (BOI12_mobile)	C++20	35 / 100	1099 ms	81008 KiB

mobile

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

using namespace std;

// Use long double for maximum precision as required by the problem.
#define ld long double
#define pr pair<ld, ld>

// This function checks if the highway is fully covered for a given radius 'd'.
// It returns 'true' if the highway is covered, 'false' otherwise.
bool isCovered(ld d, const vector<pr>& stations, ld L) {
    vector<pr> intervals;
    ld d_squared = d * d;

    for (const auto& station : stations) {
        // Skip stations that are too far vertically to ever reach the highway.
        if (d < abs(station.second)) {
            continue;
        }

        // Calculate the coverage interval on the highway (y=0 line).
        ld radius_on_highway = sqrt(d_squared - station.second * station.second);
        ld start = max((ld)0.0, station.first - radius_on_highway);
        ld end = min(L, station.first + radius_on_highway);

        // Only add valid, non-zero length intervals.
        if (start <= end) {
            intervals.push_back({start, end});
        }
    }

    // If no station provides any coverage, the highway is only "covered" if its length is zero.
    if (intervals.empty()) {
        return L <= 1e-9;
    }

    // Sort the intervals by their starting points. This is essential for the greedy strategy.
    sort(intervals.begin(), intervals.end());

    // --- The Most Robust Greedy Interval Covering Logic ---
    
    // Check for a gap at the very beginning of the highway.
    if (intervals[0].first > 1e-9) {
        return false;
    }

    ld current_coverage_end = 0.0;
    int i = 0;
    while (current_coverage_end < L) {
        ld max_reach_in_this_step = current_coverage_end;

        // From our current position, look ahead at all overlapping/adjacent intervals
        // and find the one that extends our reach the furthest.
        while (i < intervals.size() && intervals[i].first <= current_coverage_end + 1e-9) {
            max_reach_in_this_step = max(max_reach_in_this_step, intervals[i].second);
            i++;
        }

        // If we couldn't extend our coverage at all, it means there's a hole.
        // We are at 'current_coverage_end' and the next interval starts after it.
        if (max_reach_in_this_step <= current_coverage_end) {
            return false;
        }

        // Update our position to the new furthest point.
        current_coverage_end = max_reach_in_this_step;
    }

    // If the loop finishes, it means we successfully covered the entire length L.
    return true;
}

void solution() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    long long N_ll;
    ld L;
    cin >> N_ll >> L;
    int N = N_ll;

    vector<pr> stations(N);
    for (int i = 0; i < N; i++) {
        cin >> stations[i].first >> stations[i].second;
    }

    // Binary search for the answer.
    ld p = 0.0, q = 2e9; // Lower and a sufficiently large upper bound.

    // Run for a fixed number of iterations (100 is safe for 1e-4 precision).
    for (int iter = 0; iter < 100; ++iter) {
        ld mid = p + (q - p) / 2.0;
        if (isCovered(mid, stations, L)) {
            // If 'mid' works, it's a potential answer. Try for an even smaller radius.
            q = mid;
        } else {
            // If 'mid' fails, we need a larger radius.
            p = mid;
        }
    }

    // The answer is 'q', which is the smallest radius that successfully covered the highway.
    cout << q << endl;
}

int main() {
    solution();
    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: 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