Submission #1188083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188083		vosera	Mobile (BOI12_mobile)	C++20	4 / 100	149 ms	8628 KiB

mobile

#include<bits/stdc++.h>

using namespace std;

int N, L;
double r = 0, l = 1e9*sqrt(5);
vector<pair<int, int>> coor;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> L;
    for(int i = 0; i < N; i++){
        int X, Y;
        cin >> X >> Y;
        coor.push_back({X, Y});
        l = min(l, (double)abs(Y));
        r = max(r, sqrt((double)Y*Y + (double)max(X, L-X)*max(X, L-X)));
    }

    while(r-l > 1e-3){
        double mid = (r+l)/2;
        int U = -1, A = 0;
        double P = 0;
        //cout << l << " " << r << "\n";
        while(P < L){
            //cout << U << " " << P << " " << A << "\n";
            U = -1;
            for(int i = A; i < N; i++){
                if(coor[i].first < P-mid) continue;
                if(coor[i].first > P+mid) break;
                if((double)(coor[i].first-P)*(coor[i].first-P) + (double)coor[i].second*coor[i].second < mid*mid) U = i;
                //cout << "iterando: " << i << " " << ((double)(coor[i].first-P)*(coor[i].first-P) + (double)coor[i].second*coor[i].second) << " " << mid*mid << "\n";
            }
            if(U==-1){
                break;
            }
            P = abs(coor[U].first + sqrt(mid*mid - (double)coor[U].second*coor[U].second)) + 1e-3;
            A = U+1;
        }
        if(U == -1){
            l = mid;
        }
        else{
            r = mid;
        }
    }

    cout << (r+l)/2;

    return(0);
}

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