제출 #1330359

#제출 시각아이디문제언어결과실행 시간메모리
1330359randi_pavMobile (BOI12_mobile)C++20
0 / 100
1096 ms56992 KiB
#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define endl '\n'

long double get_inter(pair<ll, ll> t1, pair<ll, ll> t2) {
    long double result = (long double)t2.second * t2.second - (long double)t1.second * t1.second;
    long double result2 = t2.first - t1.first;
    long double result3 = t2.first + t1.first;
    return (result / result2 + result3) / 2.0;
}

int main() {
    fastio();
    int n, l;
    cin >> n >> l;
    vector<pair<long long, long long>> towers(n);
    for (int i = 0; i < n; i++) {
        cin >> towers[i].first >> towers[i].second;
    }

    stack<int> st;
    stack<long double> inter_st;

    for (int i = 0; i < n; i++) {
        while (st.size() >= 2) {
            long double new_inter = get_inter(towers[st.top()], towers[i]);
            if (new_inter <= inter_st.top()) {
                st.pop();
                inter_st.pop();
            } else {
                break;
            }
        }
        if (!st.empty()) {
            inter_st.push(get_inter(towers[st.top()], towers[i]));
        }
        st.push(i);
    }

    vector<int> final_towers;
    vector<long double> final_inters;
    while (!st.empty()) {
        final_towers.push_back(st.top());
        st.pop();
    }
    while (!inter_st.empty()) {
        final_inters.push_back(inter_st.top());
        inter_st.pop();
    }
    reverse(final_towers.begin(), final_towers.end());
    reverse(final_inters.begin(), final_inters.end());

    long double max_ = 0;
    max_ = max(max_, (long double)sqrtl((long double)towers[final_towers[0]].first * towers[final_towers[0]].first + (long double)towers[final_towers[0]].second * towers[final_towers[0]].second));
    max_ = max(max_, (long double)sqrtl((long double)(l - towers[final_towers.back()].first) * (l - towers[final_towers.back()].first) + (long double)towers[final_towers.back()].second * towers[final_towers.back()].second));

    for (int i = 0; i < final_inters.size(); i++) {
        long double x = final_inters[i];
        if (x < 0) x = 0;
        if (x > l) x = l;
        long double d = sqrtl((x - towers[final_towers[i]].first) * (x - towers[final_towers[i]].first) + (long double)towers[final_towers[i]].second * towers[final_towers[i]].second);
        max_ = max(max_, d);
    }

    cout << fixed << setprecision(4) << max_ << 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...