oj.uz

Submission #1096186

# Submission time Handle Problem Language Result Execution time Memory
1096186 2024-10-04T04:36:24 Z Omar_Elgedawy Mobile (BOI12_mobile) C++17
8 / 100
 195 ms 73076 KB 
#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], {x[i], y[i]}) <
            midX(st[st.size() - 2], st.back()))
        {
            st.pop_back();
        }
        st.push_back({x[i], y[i]});
    }
    while (st.size() > 2 &&
        midX(st[0], st[1]) < 0)
    {
        st.pop_front();
    }
    while (st.size() > 2 &&
        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 << mx;
}

int32_t main()
{
// #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);
// #endif
    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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 2 ms 684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3676 KB Output is correct
2 Incorrect 14 ms 3768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 14 ms 3420 KB Output is correct
3 Incorrect 18 ms 3928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6748 KB Output is correct
2 Incorrect 17 ms 4184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 36616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 24148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 44036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 28932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 51276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 33860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 58628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 38488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 73076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 48236 KB Output isn't correct
2 Halted 0 ms 0 KB -