Submission #1330382

#TimeUsernameProblemLanguageResultExecution timeMemory
1330382randi_pavMobile (BOI12_mobile)C++20
100 / 100
339 ms112240 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

typedef long double ld;

struct Tower {
    ld x, y;
};

// Intersection of (x-x1)^2 + y1^2 = (x-x2)^2 + y2^2
ld intersect(Tower a, Tower b) {
    return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2.0 * (b.x - a.x));
}

ld get_dist(Tower t, ld x) {
    return sqrtl((t.x - x) * (t.x - x) + t.y * t.y);
}

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

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

    vector<Tower> input(n);
    for(int i=0; i<n; ++i) cin >> input[i].x >> input[i].y;

    // 1. Pre-process: Filter duplicate X, keep smallest |y|
    vector<Tower> filtered;
    for(auto &t : input) {
        if(!filtered.empty() && filtered.back().x == t.x) {
            if(abs(t.y) < abs(filtered.back().y)) filtered.back() = t;
        } else filtered.push_back(t);
    }

    // 2. Build the Stack (Lower Envelope)
    // We use a vector as a stack so we can iterate through it at the end
    vector<Tower> st;
    for(auto &t : filtered) {
        while(st.size() >= 2) {
            if(intersect(st[st.size()-2], st.back()) >= intersect(st.back(), t)) 
                st.pop_back();
            else break;
        }
        st.push_back(t);
    }

    // 3. Find Max Distance by checking critical points
    ld max_d = 0;

    // Check x = 0: Which tower in the stack is closest to 0?
    // Because intersections are increasing, we find the first tower 
    // whose intersection with the next is > 0.
    int first_idx = 0;
    while(first_idx + 1 < st.size() && intersect(st[first_idx], st[first_idx+1]) <= 0) {
        first_idx++;
    }
    max_d = max(max_d, get_dist(st[first_idx], 0));

    // Check x = L: Which tower in the stack is closest to L?
    int last_idx = st.size() - 1;
    while(last_idx - 1 >= 0 && intersect(st[last_idx-1], st[last_idx]) >= l) {
        last_idx--;
    }
    max_d = max(max_d, get_dist(st[last_idx], l));

    // Check all intersections between first_idx and last_idx
    for(int i = first_idx; i < last_idx; ++i) {
        ld x_int = intersect(st[i], st[i+1]);
        // Only consider intersections within the highway bounds
        if(x_int > 0 && x_int < l) {
            max_d = max(max_d, get_dist(st[i], x_int));
        }
    }

    cout << fixed << setprecision(6) << (double)max_d << 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...