Submission #1275289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275289		sm.22	Mobile (BOI12_mobile)	C++20	0 / 100	1100 ms	95460 KiB

mobile

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
 
#define watch(x)        cerr << "\n" << (#x) << " is " << (x) << "\n";
#define int             long long 
#define ffor(i, a, b)   for(int i=a;i<b;i++)
#define rfor(i, a, b)   for(int i=a-1;i>=b;i--)
#define all(v)          v.begin(), v.end()
#define rall(v)         v.rbegin(), v.rend()
#define pb              push_back
#define fi              first
#define se              second
#define pii             pair<int, int>
#define vi              vector<int> 
#define vvi             vector<vi> 
#define show(a)         for(auto e : a) {cout<<e<<" ";} cout<<"\n"; 
#define pr(a, b, c)     ffor(i, b, c) {cout<<a[i]<<" ";} cout<<"\n";
#define cerr            if(false)cerr
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 10; 
int Mod = 1e9 + 7, INF = 1e18, BASE = 7, Block = 555;

double x[N], y[N]; 
int n, L; 

vector<double> g(int i, double far) {
        vector<double> v(2); 
        if(far*far <= y[i]) {
                return vector<double>({-1, -1}); 
                // v[0] = v[2] = 0; 
                // v[1] = v[3] = L; 
        } else {
                double s = sqrt(far * far - y[i] * y[i]);
                double l = x[i] - s, r = x[i] + s; 
                if(l < 0) l = 0; 
                if(r > L) r = L; 
                return vector<double>({l, r});
        }
        return v; 
}

bool f(double far) {

        vector<double> v = g(0, far); 
        vector<vector<double>> t;  
        if(v[0] != -1) t.pb(v); 

        ffor(i, 1, n) {
                vector<double> tmp = g(i, far);  
                if(tmp[0] != -1) t.pb(tmp);
                // now combine v & tmp 
        }

        // sort(all(t)); 
        // cout<<t.size()<<"\n"; 

        if(t.empty()) return true; 

        double l = t[0][0], r = t[0][1]; 
        ffor(i, 1, n) {
                if(t[i][0] > r) return true; 
                r = max(r, t[i][1]); 
        }

        return (l > 0 || r < L);
}

void solve() {

        cin>>n>>L; 

        ffor(i, 0, n) {
                cin>>x[i]>>y[i]; 
        }

        int l = 0, r = 1e18, m; 
        double ans = -1; 

        while(l <= r) {

                m = (l + r) / 2; 
                double d = m / (double)1e7; 

                bool yes = f(d); 

                // cout<<d<<" "<<yes<<"\n"; 

                if(yes) {
                        ans = d; 
                        l = m + 1; 
                } else r = m - 1; 
        }
        cout<<ans<<"\n"; 

}

signed main() { 
 
        ios_base::sync_with_stdio(false); 
        cin.tie(NULL); 

        int t = 1; //cin>>t; 
        cout<<fixed<<setprecision(6); 
 
        while(t--) 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