Submission #1131570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131570		dhruv05	Mobile (BOI12_mobile)	C++20	8 / 100	1099 ms	109772 KiB

mobile

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

long long int N; long double L;
vector<pair<long double, long double>> poles;

bool check(int distancee3){
    long double distance = ((long double) distancee3)/1000;
    map<long double, long long int> relevant_points;
    for (pair<long double, long double> pole: poles){

        long double left;
        long double right;
        if (abs(pole.second) > distance){
            left = L;
            right = L;
        } else {
            long double r = sqrt(pow(distance, 2) - pow(pole.second, 2));
            left = pole.first - r;
            right = pole.first + r;
        }            

        // cout << pole.first << ' ' << pole.second << ' ' << left << ' ' << right << endl;
        
        if (left < 0){
            left = 0;
        }

        if (right < 0){
            right = 0;
        }

        
        if (left < L){
            if (relevant_points.find(left) != relevant_points.end()){
                relevant_points[left]++;
            } else {
                relevant_points[left] = 1;
            }

        }

        if (right < L){
            if (relevant_points.find(right) != relevant_points.end()){
                relevant_points[right]--;
            } else {
                relevant_points[right] = -1;
            }
        }

    }

    long long int intervals_on = 0;

    if ((*relevant_points.begin()).first != 0){
        return true;
    }

    for (auto point: relevant_points){
        intervals_on += point.second;
        if (intervals_on <= 0){
            return true;
        }
    }

    return false;
}

long long int binary_search_max(long long int high, long long int low){
    while (low < high){
        long long int mid = low + (high - low + 1)/2;
        if(check(mid)){
            low = mid;
        } else{
            high = mid - 1;
        }
    }

    return low;
}

int main(){
    cin >> N >> L;

    long long int mind = LLONG_MAX;
    for (long long int i = 0; i < N; i++ ){
        long double x, y; cin >> x >> y;
        poles.push_back({x, y});
        mind = min(mind, (long long int) (max(sqrt(pow(y, 2) + pow(L - x, 2)), sqrt(pow(y, 2) + pow(x, 2)))*1000));
    }

    // cout << check(7000) << endl;
    cout << ((long double) binary_search_max(mind, 0))/1000 << endl;
}

• 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