Submission #1271650

#TimeUsernameProblemLanguageResultExecution timeMemory
1271650ZeroCoolMobile (BOI12_mobile)C++20
30 / 100
1097 ms31760 KiB
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

// #pragma GCC optimize("O3,Ofast,unroll-loops ")

const int N = 5e5 + 20;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct SGT{
    vector<set<ar<int,3> > > s;
    int n;

    SGT(){}

    SGT(int _n){
        n = _n;
        s.resize(4 * n);
    }
    
    void upd(int k,int tl,int tr,int p, int l,int r){
        if(l > tr || tl > r)return;
        if(l <= tl && tr <= r){
            s[k].insert({p, l , r});
            return;
        }
        int tm = (tl + tr) / 2;
        upd(k * 2, tl, tm, p, l, r);
        upd(k * 2 + 1, tm + 1, tr, p, l, r);
    }
    void upd(int p,int l,int r){
        upd(1, 1, n, p, l, r);
    }

    void qry(int k,int tl,int tr, int p,int l,int r,vector<ar<int,3>> &v){
        for(auto it = s[k].lower_bound(ar<int,3>{l});it != s[k].end() && ((*it)[0] <= r);it = s[k].erase(it)){
            v.push_back(*it);
        }
        if(tl == tr)return;
        int tm = (tl + tr) / 2;
        if(p <= tm)qry(k * 2, tl, tm, p, l, r, v);
        else qry(k * 2 + 1, tm + 1, tr ,p, l, r, v);
    }

    vector<ar<int,3>> qry(int p,int l,int r){
        vector<ar<int,3> > res;
        qry(1, 1, n, p,  l, r, res);
        return res;
    }
    
};

struct CMP{
    vector<int> v;

    CMP(){
        v = {0, INF};
    }

    void add(int x){
        v.push_back(x);
    }

    void init(){
        sort(all(v));
        v.erase(unique(all(v)), v.end());
    }

    int get(int x){
        return lower_bound(all(v), x) - v.begin() + 1;
    }
};

void orz(){
    int n, m;
    cin>>n>>m;
    ld x[n], y[n];
    for(int i = 0;i < n;i++)cin>>x[i]>>y[i];
    ld lo = 0;
    ld hi = 2e9;

    for(int it = 0;it < 60;it++){
        ld mid = (lo + hi) / 2;
        ld d = 0;
        for(int i = 0;i < n;i++){
            if(y[i] <= mid){
                ld l = x[i] - sqrt(mid * mid - y[i] * y[i]);
                ld r = x[i] + sqrt(mid * mid - y[i] * y[i]);
                if(l <= d)d = max(d, r);
            }
        }
        if(m <= d)hi = mid;
        else lo = mid;
    }
    cout<<setprecision(12)<<fixed<<lo<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //  cin>>t;
    while (t--)orz();
}   
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...