Submission #951177

#	Time	Username	Problem	Language	Result	Execution time	Memory
951177		Kavelmydex	Mobile (BOI12_mobile)	C++17	0 / 100	238 ms	52224 KiB

mobile

#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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5