제출 #1352895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1352895		vahagng	Mobile (BOI12_mobile)	C++20	30 / 100	1100 ms	80964 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

#define ld long double

struct Point{
    ld x, y;

};

void precision(int x){
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

const int N = 1e6 + 10;

int n;
ld l;

const ld eps = 1e-11;

Point a[N];
bool check(ld m){
    vector<pair<ld, ld>>A;
    for(int i = 1; i <= n; i++){
        if(a[i].y - eps <= m){
            ld d = sqrt(m * m - a[i].y * a[i].y);
            A.push_back({a[i].x - d, a[i].x + d});
        }
    }
    ld mx = 0.0;
    for(int i = 0; i < A.size(); i++){
        if(A[i].first - eps <= mx){
            mx = max(mx, A[i].second);
        }
    }
    return mx + eps >= l;
}

int main(){
    cin >> n >> l;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
    }
    ld l = 0.0, r = 1e10, ans = 0.0;
    for(int it = 0; it < 50; it++){
        ld m = (l + r) / 2.0;
        if(check(m)){
            r = m - 1;
            ans = m;
        }else{
            l = m + 1;
        }
    }
    precision(20);
    cout << ans << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 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