Submission #1094989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094989		Kodik	Mobile (BOI12_mobile)	C++17	0 / 100	1067 ms	105980 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
typedef long double ld;
#define int ll




bool check(const ld& l,const ld& radius,const vector<pair<ld,ld>> &bases){
    stack<pair<bool,ld>> st; // bool 1 = start, 0 end
    for(auto &[x, y] : bases){
        ld x_on_highway = sqrtl(radius*radius-y*y);
        ld start = x - x_on_highway;
        ld end = x + x_on_highway;
        bool push_start = true;
        while(!st.empty()){
            ld cor = st.top().ss; 
            /*
            if my start is earlier than last ending or starting we can remove them, at the end
            all we want not to end when there is no start
            */
            if(start<=cor){
                if(!st.top().ff){
                    push_start = 0;
                }else if(st.top().ff){
                    push_start = 1;
                }
                st.pop();
            }else{
                break;
            }
        }
        if(push_start) st.push({1,start}); // do we push start if we removed only end !no
        st.push({0,end});
    }
    bool ok = (st.size()==2);
    /*
    if everything is correct, the 
    we should have in stack only start and end
    if we dont then that means than somwhere we have a not covered interval
    */
    while(!st.empty()){
        if(ok){
            if(!st.top().ff){
                ok &= (st.top().ss>=l);
            }else if(st.top().ff){
                ok &= (st.top().ss<=0);
            }
            st.pop();
        }else{
            break;
        }
    }
    return ok;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ld n, l; 
    cin >> n >> l;
    vector<pair<ld,ld>> bases(n);
    for(int i = 0; i < n; ++i){
        ld x, y;
        cin >> x >> y;
        bases[i] = {x,abs(y)}; // shouldnt be a problem to set y to its abs
    }
    sort(bases.begin(), bases.end(), [&](const auto&a,const auto&b){
        if(a.ff==b.ff){
            return a.ss < b.ss; // we want to have the closest first, becasue it will cover the geaters interval
        }
        return a.ff < b.ff;
    });
    ld left = 0, right = 2e9;
    while(right-left>1e-7){
        ld mid = left + (right-left)/2;
        if(check(left,mid, bases)){
            // ak sedi zmensujem
            right = mid;
        }else{
            left = mid;
        }
    }
    cout << fixed << setprecision(3) << right;
    return 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