제출 #1330378

#제출 시각아이디문제언어결과실행 시간메모리
1330378randi_pavMobile (BOI12_mobile)C++20
100 / 100
352 ms112288 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

typedef long double ld;

struct Station {
    ld x, y;
};

// Intersection of two parabolas (x-x1)^2 + y1^2 = (x-x2)^2 + y2^2
ld get_intersect(Station s1, Station s2) {
    return (s2.x * s2.x + s2.y * s2.y - s1.x * s1.x - s1.y * s1.y) / (2.0 * (s2.x - s1.x));
}

ld dist_sq(Station s, ld x) {
    return (s.x - x) * (s.x - x) + s.y * s.y;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ld l;
    if (!(cin >> n >> l)) return 0;

    vector<Station> temp(n);
    for (int i = 0; i < n; i++) {
        cin >> temp[i].x >> temp[i].y;
    }

    // 1. Filter: If x is same, keep only the one with smaller |y|
    vector<Station> filtered;
    for (auto& s : temp) {
        if (!filtered.empty() && filtered.back().x == s.x) {
            if (abs(s.y) < abs(filtered.back().y)) {
                filtered.back() = s;
            }
        } else {
            filtered.push_back(s);
        }
    }

    // 2. Build the Lower Envelope (The Stack)
    vector<Station> hull;
    for (auto& s : filtered) {
        // While the new station 's' makes the previous station in the hull redundant
        while (hull.size() >= 2) {
            ld x12 = get_intersect(hull[hull.size() - 2], hull.back());
            ld x23 = get_intersect(hull.back(), s);
            if (x23 <= x12) {
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(s);
    }

    // 3. Find the maximum distance along the highway [0, L]
    // The max distance must occur at 0, L, or at an intersection point.
    ld max_d2 = 0;
    
    // Check start and end points
    // We need to find which station in the hull is closest to x=0 and x=L
    // Since intersections are sorted, we can find them efficiently.
    
    auto get_min_dist_at_x = [&](ld x_pos) {
        int low = 0, high = hull.size() - 1;
        int best_idx = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == (int)hull.size() - 1 || get_intersect(hull[mid], hull[mid+1]) > x_pos) {
                best_idx = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return dist_sq(hull[best_idx], x_pos);
    };

    max_d2 = max(get_min_dist_at_x(0), get_min_dist_at_x(l));

    // Check all relevant intersection points within the range (0, L)
    for (int i = 0; i < (int)hull.size() - 1; i++) {
        ld x_int = get_intersect(hull[i], hull[i+1]);
        if (x_int > 0 && x_int < l) {
            max_d2 = max(max_d2, dist_sq(hull[i], x_int));
        }
    }

    cout << fixed << setprecision(6) << sqrtl(max_d2) << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...