Submission #1096190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096190		Omar_Elgedawy	Mobile (BOI12_mobile)	C++17	100 / 100	225 ms	64340 KiB

mobile

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ld long double
#define F first
#define S second
#define el '\n'
#define cout(x) for(auto v:x)cout<<v<<el
#define coutp(x) for(auto v:x)cout<<v.F<<' '<<v.S<<el
#define cin(x) for(auto &v:x)cin>>v;
#define pb(x) push_back(x)
#define all(x)  x.begin(),x.end()

const int N = 5e3 + 5, M = 1e2 + 5, Mod = 1e9 + 7;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};

int nxt()
{
    int x;
    cin >> x;
    return x;
}

ld midX(pair<ld,ld> a, pair<ld,ld> b)
{
    return (b.F * b.F + b.S * b.S - a.F * a.F - a.S * a.S) / (2 * b.F - 2 * a.F);
}

ld dist(pair<ld,ld> a, pair<ld,ld> b)
{
    return sqrtl((a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S));
}

void solve(int h)
{
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> v;
    ld x[n], y[n];
    deque<pair<ld,ld>> st;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        x[i] = a;
        y[i] = abs(b);
        if (st.size() && st.back().F == x[i])
        {
            if (st.back().S <= y[i])
            {
                continue;
            }
            else
            {
                st.pop_back();
            }
        }
        while (st.size() > 1 &&
            midX(st[st.size() - 2], st.back()) >
            midX(st.back(), {x[i], y[i]}))
        {
            st.pop_back();
        }
        st.push_back({x[i], y[i]});
    }
    while (st.size() > 1 &&
        midX(st[0], st[1]) < 0)
    {
        st.pop_front();
    }
    while (st.size() > 1 &&
        midX(st.back(), st[st.size() - 2]) > m)
    {
        st.pop_back();
    }
    ld mx = 0;
    for (int i = 0; i < st.size(); i++)
    {
        pair<ld,ld> left = {0, 0}, right = {m, 0};
        if (i)left.F = midX(st[i], st[i - 1]);
        if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
        if (left.F < 0 || left.F > m || right.F < 0 || right.F > m)
            continue;
        mx = max({mx, dist(st[i], left), dist(st[i], right)});
    }
    cout << fixed<<setprecision(4)<<mx;
}

int32_t main()
{
// #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 // #endif
    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; i++)solve(i);
    return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'void solve(long long int)':
mobile.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < st.size(); i++)
      |                     ~~^~~~~~~~~~~
mobile.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
      |             ~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5