oj.uz

Submission #1096187

# Submission time Handle Problem Language Result Execution time Memory
1096187 2024-10-04T04:39:14 Z Omar_Elgedawy Mobile (BOI12_mobile) C++17
0 / 100
 141 ms 31576 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.back(), {x[i], y[i]}))
        {
            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);
 // #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

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

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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