Submission #1119533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119533		awesomemaths	Mobile (BOI12_mobile)	C++17	0 / 100	1057 ms	131072 KiB

mobile

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define print(x) cout << (x) << endln
#define each(a, x) for(auto &&a : x)

using namespace std;

const int inf = 1LL<<60;

long double distance(pair<ld,ld> a, pair<ld,ld> b){
    ld res = (b.ff-a.ff)*(b.ff-a.ff)+(b.ss-a.ss)*(b.ss-a.ss);
    return res;
}

ld xcept(pair<ld,ld> a, pair<ld,ld> b){
    if(a.ss == b.ss){
        ld mid = (a.ff+b.ff)/2;
        return mid;
    }
    pair<ld,ld>  res;
    res.ff = (a.ff+b.ff)/2;
    res.ss = (a.ss+b.ss)/2;
    ld slope = -(b.ff-a.ff)/(b.ss-a.ss);
    ld c = res.ss-res.ff*slope;
    ld x = -c/slope;
    return x;
}

void solve(){
    int n,l;
    cin >> n >> l;
    vector<pair<ld,ld>> p(n);
    for(int i=0;i<n;i++){
        ld x,y;
        cin >> x >> y;
        p[i] = {x,y};
    }
    ld ans = -1;
    sort(p.begin(),p.end()); //remove garbage values
    map<pair<ld,ld>,ld> m;
    stack<tuple<ld,ld,int>> stck;
    m[{0,0}] = distance({0,0},p[0]);
    m[{l,0}] = distance({l,0},p[0]);
    stck.push({0,l,0});
    for(int i=1;i<n;i++){
        while(true && stck.size()){
            int last = get<2>(stck.top());
            ld res = xcept(p[last],p[i]);
            if(res>l) continue;
            int left =get<0>(stck.top());
            if(res<=left){
                stck.pop();
            } else{
                break;
            }
        }
        if(stck.size()==0){
            stck.push({0,l,i});
            m[{0,0}] = distance({0,0},p[i]);
            m[{l,0}] = distance({l,0},p[i]);
        } else{
            int last = get<2>(stck.top());
            ld res = xcept(p[last],p[i]);
            int left =get<0>(stck.top());
            stck.pop();
            stck.push({left,res,last});
            ld z = distance(p[last],{res,0});
            m[{res,0}] = z;
            stck.push({res,l,i});
            z = distance(p[i],{l,0});
            m[{l,0}] = z;
        }
    }
    for(auto x : m){
        ans = max(ans,x.ss);
    }
    cout << sqrt(ans) << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    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