oj.uz

Submission #1064682

# Submission time Handle Problem Language Result Execution time Memory
1064682 2024-08-18T16:51:31 Z daviedu Mobile (BOI12_mobile) C++17
100 / 100
 379 ms 41808 KB 
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ld long double

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

ld border(ld x, ld y, ld a, ld b){
    return (a*a + b*b - x*x - y*y) / (2*a - 2*x);
}

ld dist(ld x, ld y, ld point){
    return sqrtl(y*y + (point-x)*(point-x));
}

signed main(){
    fastio;
    int n, r;
    cin >> n >> r;
    stack<pair<ld, ld>> st;
    // this will be useful for simplifying implementation later
    st.push({-2e9, -2e9});
    ld a, b, x, y;
    for (int i=0; i<n; i++){
        cin >> a >> b;
        if (b < 0) b = -b;
        
        while (!st.empty() && st.top().first == a && st.top().second > b) st.pop();

        while ((int)st.size() > 1){
            tie(x, y) = st.top();
            st.pop();

            // if prev is not a useless point, put it back and stop
            if (border(x, y, a, b) > border(st.top().first, st.top().second, x, y)){
                st.push({x, y});
                break;
            }
        }

        st.push({a, b});
    }
    ld ans=0;
    ld right=r;
    while ((int)st.size() > 1){
        tie(a, b) = st.top();
        st.pop();
        tie(x, y) = st.top();
        ld left = border(x, y, a, b);
        
        // not in some interesting range yet
        if (left >= right) continue;

        ans = max(ans, dist(a, b, right));
        ans = max(ans, dist(a, b, max(left, (ld)0)));
        
        // from here onwards we will be looking at non interesting ranges
        if (left <= 0) break;
        right = left;
    }

    cout << fixed << setprecision(13);
    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 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
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1368 KB Output is correct
2 Correct 24 ms 1352 KB Output is correct
3 Correct 16 ms 1132 KB Output is correct
4 Correct 27 ms 1624 KB Output is correct
5 Correct 14 ms 856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1116 KB Output is correct
2 Correct 24 ms 1092 KB Output is correct
3 Correct 27 ms 1372 KB Output is correct
4 Correct 30 ms 1628 KB Output is correct
5 Correct 32 ms 1884 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3924 KB Output is correct
2 Correct 26 ms 1608 KB Output is correct
3 Correct 26 ms 3676 KB Output is correct
4 Correct 39 ms 2356 KB Output is correct
5 Correct 28 ms 1372 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1884 KB Output is correct
2 Correct 36 ms 1620 KB Output is correct
3 Correct 29 ms 1884 KB Output is correct
4 Correct 39 ms 2236 KB Output is correct
5 Correct 34 ms 1600 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3920 KB Output is correct
2 Correct 33 ms 1872 KB Output is correct
3 Correct 37 ms 1780 KB Output is correct
4 Correct 42 ms 2372 KB Output is correct
5 Correct 33 ms 1732 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 21116 KB Output is correct
2 Correct 168 ms 8016 KB Output is correct
3 Correct 188 ms 7508 KB Output is correct
4 Correct 186 ms 9808 KB Output is correct
5 Correct 183 ms 7096 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 8536 KB Output is correct
2 Correct 194 ms 8784 KB Output is correct
3 Correct 153 ms 9296 KB Output is correct
4 Correct 216 ms 9664 KB Output is correct
5 Correct 168 ms 7760 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 25112 KB Output is correct
2 Correct 190 ms 9900 KB Output is correct
3 Correct 188 ms 9040 KB Output is correct
4 Correct 229 ms 12112 KB Output is correct
5 Correct 203 ms 8276 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 10068 KB Output is correct
2 Correct 201 ms 9996 KB Output is correct
3 Correct 175 ms 9308 KB Output is correct
4 Correct 226 ms 12116 KB Output is correct
5 Correct 211 ms 9048 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 29412 KB Output is correct
2 Correct 222 ms 11092 KB Output is correct
3 Correct 214 ms 10580 KB Output is correct
4 Correct 259 ms 13880 KB Output is correct
5 Correct 228 ms 9296 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11856 KB Output is correct
2 Correct 224 ms 11452 KB Output is correct
3 Correct 217 ms 12976 KB Output is correct
4 Correct 257 ms 13652 KB Output is correct
5 Correct 236 ms 10576 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 33536 KB Output is correct
2 Correct 257 ms 12844 KB Output is correct
3 Correct 253 ms 11956 KB Output is correct
4 Correct 300 ms 16048 KB Output is correct
5 Correct 277 ms 11604 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 13396 KB Output is correct
2 Correct 258 ms 12876 KB Output is correct
3 Correct 272 ms 13912 KB Output is correct
4 Correct 330 ms 15916 KB Output is correct
5 Correct 297 ms 11856 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 41808 KB Output is correct
2 Correct 313 ms 15952 KB Output is correct
3 Correct 307 ms 14932 KB Output is correct
4 Correct 369 ms 19540 KB Output is correct
5 Correct 339 ms 13888 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 16808 KB Output is correct
2 Correct 334 ms 15844 KB Output is correct
3 Correct 300 ms 17748 KB Output is correct
4 Correct 379 ms 19780 KB Output is correct
5 Correct 350 ms 15188 KB Output is correct