Submission #768929

#	Time	Username	Problem	Language	Result	Execution time	Memory
768929		orcslop	Mobile (BOI12_mobile)	C++17	0 / 100	1085 ms	48100 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 1e6; 

int n; 
double l; 
pair<double, double> v[MAXN]; 

bool check(double rad){
    vector<pair<double, double>> intervals; 
    for(int i = 0; i < n; i++){
        if(v[i].second >= rad) continue; 
        pair<double, double> add; 
        add.first = min(l, max(v[i].first - sqrt(rad * rad - v[i].second * v[i].second), (double)0)); 
        add.second = max((double)0, min(v[i].first  + sqrt(rad * rad - v[i].second * v[i].second), l)); 
        intervals.push_back(add); 
    }
    sort(intervals.begin(), intervals.end()); 
    if(intervals.empty() || intervals[0].first != 0 || intervals.back().second != l) return false; 
    double curr = intervals[0].second; 
    for(auto x : intervals) {
        if(x.first > curr) return false; 
        else curr = x.second; 
    }
    return true; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> l; 
    for(int i = 0; i < n; i++){
        cin >> v[i].first >> v[i].second; 
    }
    // cout << check(5.55); 
    double low = 0, high = (double) 1e8; 
    while (low + 0.0000001 < high) {
        double mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    cout << setprecision(15) << low << '\n'; 
    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