oj.uz

Submission #951177

# Submission time Handle Problem Language Result Execution time Memory
951177 2024-03-21T10:01:35 Z Kavelmydex Mobile (BOI12_mobile) C++17
0 / 100
 238 ms 52224 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define endl "\n"
#define sp ' '
#define pb push_back
#define f first
#define s second
#define sz size()
#define all(x) (x).begin(),(x).end()
 
const int N = 1e6+1, OO = 1e18, mod = 1e9;
void tr(int a, int b){cout << a << sp << b << endl;}
void cmx(double &a, double b){a = max(a,b);}
void cmn(double &a, double b){a = min(a,b);}

pi p[N];
deque <pi> v, u;
int n,l; 
double mn1 = OO, mn2 = OO, ans = 0;
int fun(int j){
    if(u.sz == 1) return j ? -OO: OO;
    int X = abs(u[0].f - u[1].f);
    int d = ( u[0].s * u[0].s - u[1].s * u[1].s + X * X ) / (-2*X);
    return d;
}
void deb(){
    deque <pi> t;
    For(i,n){
        int j = i, mn = OO;
        while(j < n && v[i].f == v[j].f) mn = min(mn, v[j].s), j++;
        t.pb(v[i]);
        i = j-1;
    }
    v = t; n = v.sz;
}
double calc(pi L, pi R){
    double X = abs(R.f - L.f);
    if(L.s*L.s + X*X <= R.s*R.s) return sqrt(L.s*L.s + X*X);
    if(R.s*R.s + X*X <= L.s*L.s) return sqrt(R.s*R.s + X*X);
    double d = ( R.s * R.s - L.s * L.s + X*X ) / (2*X), dist = sqrt(d*d + L.s*L.s);
    if(R.f >= 0 && L.f >= 0){
        return dist;          
    }
    if(R.f > l && L.f <= l){
        if(L.f + d < l)
            return dist;
    }
    if(L.f < 0 && R.f >= 0){
        if(R.f - d > 0)
            return dist;
    }
    return 0;
}
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    For(i,n){
        int x,y; cin >> x >> y;
        y = abs(y);
        v.pb({x,y});
    }
    deb();
    u.pb(v[0]);
    for(int i=1; i<n; ++i){
        auto [x,y] = v[i];
        while(u.sz > 1 && fun(0) + u.front().f < x){
            u.pop_front(); 
            while(fun(0) < 0) u.pop_front();
        }
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();
        p[i-1] = u.front();
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        } else {
            u.clear(); 
            u.pb(v[i]);
        }
    } u.clear();
    for(auto [x,y]: v){
        cmn(mn1, sqrt(x*x+y*y));
        cmn(mn2, sqrt(abs(x-l)*abs(x-l)+y*y));
    }
    cmx(ans, max(mn1,mn2));
    u.pb(v[n-1]);
    for(int i=n-2; i>=0; --i){
        auto [x,y] = v[i];
        while(u.sz > 1 && -fun(1) + u.front().f > x){
            u.pop_front(); 
            while(fun(1) > 0) u.pop_front();
        } 
        while(u.sz && u.back().s * u.back().s >= (abs(x-u.back().f)*abs(x-u.back().f) + y*y)) u.pop_back();

        cmx(ans,calc(p[i], u.front()));
        if(u.sz && abs(u.front().f-x) * abs(u.front().f-x) + u.front().s * u.front().s <= y*y){
            u.pb(v[i]);
        }else {
            u.clear(); 
            u.pb(v[i]);
        }
    }
    cout << fixed << setprecision(4) << ans << endl;
    return 0;
}
/*
7 14
2 1
3 3
4 3
7 5
11 3
12 2
14 0
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 600 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 604 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 16 ms 4624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4780 KB Output is correct
2 Correct 16 ms 4832 KB Output is correct
3 Incorrect 15 ms 5228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4508 KB Output is correct
2 Correct 18 ms 4928 KB Output is correct
3 Incorrect 13 ms 4632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5492 KB Output is correct
2 Correct 17 ms 4936 KB Output is correct
3 Incorrect 13 ms 4628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 19360 KB Output is correct
2 Correct 72 ms 16296 KB Output is correct
3 Correct 73 ms 15972 KB Output is correct
4 Incorrect 134 ms 26552 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 23488 KB Output is correct
2 Correct 102 ms 19604 KB Output is correct
3 Correct 81 ms 19084 KB Output is correct
4 Incorrect 154 ms 32700 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 27808 KB Output is correct
2 Correct 104 ms 23008 KB Output is correct
3 Correct 95 ms 21996 KB Output is correct
4 Incorrect 168 ms 37896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 32060 KB Output is correct
2 Correct 114 ms 25828 KB Output is correct
3 Correct 117 ms 25312 KB Output is correct
4 Incorrect 210 ms 43724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 37620 KB Output is correct
2 Correct 150 ms 32296 KB Output is correct
3 Correct 137 ms 31300 KB Output is correct
4 Incorrect 238 ms 52224 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

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