Submission #1339226

#TimeUsernameProblemLanguageResultExecution timeMemory
1339226mernakMobile (BOI12_mobile)C++20
0 / 100
144 ms28772 KiB
#include <bits/stdc++.h>
using namespace std;
namespace shortages {
    using ll = long long;
    using ull = unsigned long long;
    using uint = unsigned int;
    using ld = long double;

    template <typename T>
    using vec = vector<T>;

    template <typename T>
    using vv = vector<vector<T>>;

    template <typename T1, typename T2>
    ostream& operator<<(ostream& os, const pair<T1, T2>& pa) {
        os << pa.first << ' ' << pa.second;
        return os;
    }

    template <typename T1, typename T2>
    istream& operator>>(istream& is, pair<T1, T2>& pa) {
        is >> pa.first >> pa.second;
        return is;
    }

    template <typename T>
    ostream& operator<<(ostream& os, const vector<T>& vec) {
        for (size_t i = 0; i < vec.size(); ++i) {
            os << vec[i];
            if (i + 1 < vec.size())
                os << ' ';
        }
        os << '\n';
        return os;
    }

    template <typename T1, typename T2>
    ostream& operator<<(ostream& os, const vector<pair<T1, T2>>& vec) {
        for (size_t i = 0; i < vec.size(); ++i) {
            os << vec[i].first << ' ' << vec[i].second;
            if (i + 1 < vec.size())
                os << '\n';
        }
        return os;
    }

    template <typename T>
    ostream& operator<<(ostream& os, const vector<vector<T>>& vec) {
        for (size_t i = 0; i < vec.size(); ++i)
            os << vec[i];
        os << '\n';
        return os;
    }

    template <typename T>
    istream& operator>>(istream& is, vector<T>& vec) {
        for (auto& x : vec)
            is >> x;
        return is;
    }

    #define pint pair<int,int>
    #define pll pair<ll, ll>
    #define vi vec<int>
    #define vll vec<ll>
    #define vvi vec<vec<int>>
    #define vvll vec<vec<ll>>
    #define all(v) v.begin(), v.end()
}
using namespace shortages;

bool ith_bit(int n, int i) {
    return (n >> i) & 1;
}

void answer(bool ans) {
    if (ans)
        cout << "Yes\n";
    else
        cout << "No\n";
}


constexpr ll INF = 1e18;
constexpr ll M = 998244353;

ld d(pint p, pint q) {
    ll x=p.first,y=p.second,z=q.first,t=q.second;
    return (ld) (z * z + t * t - x * x - y*y) / (2 * (z - x));
}

ld dist(pint p, pair<ld, ld> q) {
    ld x=p.first,y=p.second,z=q.first,t=q.second;
    return sqrt((x - z) * (x - z) + (y - t) * (y - t));
}

void solve() {
    int n, l;
    cin >> n >> l;
    vec<pint> a;
    for (int i = 0; i < n; ++i) {
        pint p;
        cin >> p;
        if (!a.empty()) {
            pint q = a.back();
            if (q.first == p.first) {
                a.pop_back();
                pint r = {q.first, min(abs(p.second), abs(q.second))};
                a.push_back(r);
            }
            else
                a.push_back(p);
        }
        else
            a.push_back(p);
    }
    stack<pint> s;
    for (auto p : a) {
        while (s.size() >= 2) {
            pint q = s.top(); s.pop();
            if (d(p, q) >= d(q, s.top())) {
                s.push(q);
                break;
            }
        }
        s.push(p);
    }
    vec<pint> v;
    while (!s.empty()) {
        pint q = s.top(); s.pop();
        v.push_back(q);
    }
    reverse(all(v));
    ld res = 0;
    for (int i = 0; i < v.size() - 1; ++i) {
        ld val = d(v[i], v[i + 1]);
        if (val >= 0 && val <= l)
            res = max(res, dist(v[i], {val, 0}));
    }
    res = max(res, dist(v.front(), {0, 0}));
    res = max(res, dist(v.back(),  {l, 0}));
    cout << fixed << setprecision(6) << res << '\n';
}


int main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //freopen("paintbarn.in", "r", stdin);
    //freopen("paintbarn.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test--)
        solve();
    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...