Submission #1063939

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063939	2024-08-18T06:24:36 Z	daviedu	Mobile (BOI12_mobile)	C++17	100 / 100	396 ms	33084 KB

mobile

#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;
    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);
        if (left >= right) continue;
        if (right >= 0 && right <= r) ans = max(ans, dist(a, b, right));
        if (left >= 0 && left <= r) ans = max(ans, dist(a, b, left));
        if (left < 0 && right >= 0) ans = max(ans, dist(a, b, 0));
        right = left;
    }
    tie(a, b) = st.top();
    if (right >= 0) {
        ans = max(ans, dist(a, b, right));
        ans = max(ans, dist(a, b, 0));
    }
    cout << fixed << setprecision(13);
    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 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	348 KB	Output is correct

Subtask #4
4.0 / 4.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	348 KB	Output is correct

Subtask #5
4.0 / 4.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	2 ms	348 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 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	344 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	560 KB	Output is correct
2	Correct	23 ms	348 KB	Output is correct
3	Correct	16 ms	1140 KB	Output is correct
4	Correct	30 ms	1604 KB	Output is correct
5	Correct	14 ms	860 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	344 KB	Output is correct
2	Correct	28 ms	596 KB	Output is correct
3	Correct	28 ms	344 KB	Output is correct
4	Correct	35 ms	348 KB	Output is correct
5	Correct	31 ms	452 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	3160 KB	Output is correct
2	Correct	25 ms	472 KB	Output is correct
3	Correct	26 ms	3664 KB	Output is correct
4	Correct	39 ms	2388 KB	Output is correct
5	Correct	27 ms	1340 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	344 KB	Output is correct
2	Correct	33 ms	1860 KB	Output is correct
3	Correct	29 ms	1884 KB	Output is correct
4	Correct	37 ms	2416 KB	Output is correct
5	Correct	32 ms	1616 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	2480 KB	Output is correct
2	Correct	32 ms	348 KB	Output is correct
3	Correct	29 ms	1884 KB	Output is correct
4	Correct	41 ms	2252 KB	Output is correct
5	Correct	43 ms	1736 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	16644 KB	Output is correct
2	Correct	159 ms	348 KB	Output is correct
3	Correct	148 ms	344 KB	Output is correct
4	Correct	177 ms	456 KB	Output is correct
5	Correct	161 ms	348 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	348 KB	Output is correct
2	Correct	153 ms	2044 KB	Output is correct
3	Correct	161 ms	3452 KB	Output is correct
4	Correct	183 ms	464 KB	Output is correct
5	Correct	162 ms	348 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	19976 KB	Output is correct
2	Correct	195 ms	348 KB	Output is correct
3	Correct	206 ms	9040 KB	Output is correct
4	Correct	217 ms	12348 KB	Output is correct
5	Correct	199 ms	8376 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	344 KB	Output is correct
2	Correct	208 ms	2132 KB	Output is correct
3	Correct	168 ms	2384 KB	Output is correct
4	Correct	216 ms	12112 KB	Output is correct
5	Correct	197 ms	9140 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	23380 KB	Output is correct
2	Correct	232 ms	348 KB	Output is correct
3	Correct	214 ms	10412 KB	Output is correct
4	Correct	298 ms	13996 KB	Output is correct
5	Correct	243 ms	9276 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	700 KB	Output is correct
2	Correct	237 ms	2384 KB	Output is correct
3	Correct	218 ms	4372 KB	Output is correct
4	Correct	255 ms	13752 KB	Output is correct
5	Correct	236 ms	10416 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	26624 KB	Output is correct
2	Correct	253 ms	440 KB	Output is correct
3	Correct	283 ms	11836 KB	Output is correct
4	Correct	298 ms	15928 KB	Output is correct
5	Correct	261 ms	11604 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	440 KB	Output is correct
2	Correct	296 ms	2384 KB	Output is correct
3	Correct	242 ms	4436 KB	Output is correct
4	Correct	299 ms	15928 KB	Output is correct
5	Correct	265 ms	11824 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	303 ms	33084 KB	Output is correct
2	Correct	346 ms	440 KB	Output is correct
3	Correct	308 ms	14904 KB	Output is correct
4	Correct	376 ms	19540 KB	Output is correct
5	Correct	356 ms	13904 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	340 ms	348 KB	Output is correct
2	Correct	325 ms	2464 KB	Output is correct
3	Correct	300 ms	5456 KB	Output is correct
4	Correct	396 ms	604 KB	Output is correct
5	Correct	341 ms	344 KB	Output is correct

Submission #1063939

Compilation message