Submission #1241292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241292		Zero	Mobile (BOI12_mobile)	C++20	0 / 100	1099 ms	48172 KiB

mobile

#include <bits/stdc++.h>
#define f first
#define ss second
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.ss == b.ss) return a.f<b.f;
    return a.ss<b.ss;
}
bool ok(double m, vector<pair<int,int>> a, int x){
    int n = a.size();
    vector<pair<double,double>> b;
    for(int i=0; i < n; i ++){
        double le = a[i].f-sqrt(m*m-a[i].ss*a[i].ss), re = a[i].f+sqrt(m*m-a[i].ss*a[i].ss);
        if(abs(a[i].ss) > m) return 0;
        b.push_back({le,re});
    }
    sort(b.begin(),b.end(),cmp);
    if(b[0].f > 0 || b[n-1].ss<x) return 0;
    for(int i=1; i < n; i ++){
        if(b[i].f<0 && b[i].ss <0) continue;
        if(b[i].f>0 && b[i-1].ss >=0 && b[i].f > b[i-1].ss) return 0;
        if(b[i].f>=x && b[i].ss>=x) break;
    }
    // for(int i=0; i < n; i ++){
    //     cout << b[i].f <<"-" << b[i].ss <<" ";
    // }
    return 1;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x; cin >> n >> x;
    vector<pair<int,int>> a(n);
    for(auto &i : a) cin >> i.first >> i.second;
    
    double l = 0, r = INT_MAX;
    for(int i=0; i < 100; i ++){
        double m = (l + r) / 2;
        if(ok(m,a,x)) r = m;
        else l=m;
    }
    // ok(5.099020,a,x);
    cout << fixed << setprecision(6) << r;
}

• 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