Submission #963064

#	Time	Username	Problem	Language	Result	Execution time	Memory
963064		alecurse	Mobile (BOI12_mobile)	C++17	8 / 100	1018 ms	48208 KiB

mobile

#include <iostream>
#include <vector>
#include <math.h>
#define mp make_pair
using namespace std;
int N, L;
vector<pair<double,double> > points;
vector<pair<double,double> > segs;
bool test(double r) {
    for(int i=0;i<N;i++) {
        double x = points[i].first, y=points[i].second;
        if(r<y) {
            segs[i].first=-1;
            continue;
        }
        double d = sqrt(r*r-y*y);
        segs[i].first=x-d;
        segs[i].second=x+d;
    }
    double left=0;
    for(int i=0;i<N;i++) {
        if(segs[i].first==-1) {
            continue;
        }
        if(segs[i].first<=left) {
            left=max(left,segs[i].second);
        }
    }
    return left>=L;
}


int main() {
    cin>>N>>L;
    segs.resize(N);
    points.resize(N);
    for(int i=0;i<N;i++) {
        cin>>points[i].first>>points[i].second;
    }
    double a = 0, b=1e9;
    double res=1e9;
    while(abs(a-b)>=1e-4) {
        double k=(a+b)/2;
        if(test(k)) {
            res=min(res,k);
            b=k;
        } else {
            a=k;
        }
    }
    cout<<res;
}

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