제출 #1163630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163630		kedimestan	Mobile (BOI12_mobile)	C++20	0 / 100	1096 ms	15944 KiB

mobile

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

struct Station {
    long long x, y;
};

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

    int N;
    long long L;
    cin >> N >> L;
    vector<Station> stations(N);
    for (int i = 0; i < N; i++) {
        cin >> stations[i].x >> stations[i].y;
    }

    // Function to compute the distance from a highway point x to its nearest BTS
    auto nearestDistance = [&](double x) -> double {
        // Binary search for the first station with x-coordinate >= x
        int lo = 0, hi = N;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (stations[mid].x < x)
                lo = mid + 1;
            else
                hi = mid;
        }

        double best = 1e18;
        // Check station at or after x
        if (lo < N) {
            double dx = x - stations[lo].x;
            double dist = sqrt(dx * dx + (double)stations[lo].y * stations[lo].y);
            best = min(best, dist);
        }
        // Check station immediately before x (if exists)
        if (lo - 1 >= 0) {
            double dx = x - stations[lo - 1].x;
            double dist = sqrt(dx * dx + (double)stations[lo - 1].y * stations[lo - 1].y);
            best = min(best, dist);
        }
        return best;
    };
    
    // Binary search on the highway [0, L] for the maximum distance
    double left = 0.0, right = (double)L;
    double maxDist = 0.0;
    const double eps = 1e-9;  // Increased precision

    while (right - left > eps) {
        double mid = (left + right) / 2.0;
        double dMid = nearestDistance(mid);
        double dMidEps = nearestDistance(mid + eps);

        maxDist = max(maxDist, dMid);

        // Compare the distances at mid and mid + eps to determine the direction
        if (dMid < dMidEps) {
            left = mid;  // move right if function is increasing
        } else {
            right = mid; // move left if function is decreasing
        }
    }

    cout << fixed << setprecision(6) << maxDist << "\n";
    return 0;
}

• 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