Submission #1314335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314335		ashikur_	Mobile (BOI12_mobile)	C++20	In queue	0 ms	0 KiB

mobile

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define inf (ll)1e15
#define ll long long
#define lll __int128_t
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define mod 1000000007
// #define mod 998244353
#define pie acos(-1.0)
#define LSOne(i) ((i) & -(i))
#define EPS 1e-9

struct point{
    double x, y;
};

double dist(point a, point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double val(vector<point> &vtr, double x){
    double ans = -inf;
    for(point p : vtr){
        ans = max(ans, dist({x, 0}, p));
    }
    return ans;
}

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m; cin >> n >> m;
    vector<point> vtr(n);
    for(ll i = 0; i < n; i++) cin >> vtr[i].x >> vtr[i].y;

    double lo = 0, hi = m, ans;
    for(int i = 0; i <= 50; i++){
        double m1 = lo + (hi-lo)/3;
        double m2 = hi - (hi-lo)/3;
        
        double val1 = val(vtr, m1);
        double val2 = val(vtr, m2);

        if(val1 <= val2){
            hi = m2, ans = val1;
        } else{
            lo = m1, ans = val2;
        }
    }
    cout << fixed << setprecision(5) << ans << "\n";
}