oj.uz

Submission #768938

# Submission time Handle Problem Language Result Execution time Memory
768938 2023-06-28T23:44:01 Z orcslop Mobile (BOI12_mobile) C++17
100 / 100
 672 ms 35324 KB 
#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; 
    double curr = 0; 
    for(int i = 0; i < n; i++){
        double dist = 0; 
        if(0 <= v[i].first && v[i].first <= l){
            dist = v[i].second; 
        }
        else if(v[i].first < 0){
            dist = sqrt(v[i].first * v[i].first + v[i].second + v[i].second); 
        }
        else {
            dist=sqrt((v[i].first-l) * (v[i].first - l) + v[i].second * v[i].second); 
        }
        if(dist < rad){
            pair<double, double> range; 
            range.first = v[i].first - sqrt(rad * rad - v[i].second * v[i].second);
            range.second = v[i].first + sqrt(rad * rad - v[i].second * v[i].second); 
            if(range.first <= curr) curr = max(curr, range.second); 
            // else return false; 
        }
    }
    return curr >= l; 
}

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) 2e9; 
    while (low + 0.00001 < high) {
        double mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    cout << setprecision(15) << low << '\n'; 
    return 0; 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 456 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 404 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 412 KB Output is correct
5 Correct 3 ms 376 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1736 KB Output is correct
2 Correct 42 ms 2588 KB Output is correct
3 Correct 27 ms 1792 KB Output is correct
4 Correct 51 ms 2672 KB Output is correct
5 Correct 25 ms 1464 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1764 KB Output is correct
2 Correct 42 ms 2216 KB Output is correct
3 Correct 49 ms 2560 KB Output is correct
4 Correct 55 ms 2676 KB Output is correct
5 Correct 58 ms 3220 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1796 KB Output is correct
2 Correct 45 ms 2360 KB Output is correct
3 Correct 39 ms 2244 KB Output is correct
4 Correct 66 ms 3784 KB Output is correct
5 Correct 52 ms 2556 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2136 KB Output is correct
2 Correct 54 ms 3272 KB Output is correct
3 Correct 49 ms 2900 KB Output is correct
4 Correct 66 ms 3820 KB Output is correct
5 Correct 59 ms 3100 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2012 KB Output is correct
2 Correct 54 ms 2128 KB Output is correct
3 Correct 45 ms 2252 KB Output is correct
4 Correct 66 ms 3736 KB Output is correct
5 Correct 60 ms 3064 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 8284 KB Output is correct
2 Correct 276 ms 9104 KB Output is correct
3 Correct 273 ms 12504 KB Output is correct
4 Correct 339 ms 12584 KB Output is correct
5 Correct 302 ms 14884 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 8392 KB Output is correct
2 Correct 261 ms 8392 KB Output is correct
3 Correct 222 ms 13776 KB Output is correct
4 Correct 330 ms 17480 KB Output is correct
5 Correct 311 ms 15440 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 9896 KB Output is correct
2 Correct 339 ms 14184 KB Output is correct
3 Correct 332 ms 18364 KB Output is correct
4 Correct 399 ms 21612 KB Output is correct
5 Correct 359 ms 17612 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 9956 KB Output is correct
2 Correct 312 ms 9984 KB Output is correct
3 Correct 300 ms 16636 KB Output is correct
4 Correct 394 ms 21372 KB Output is correct
5 Correct 378 ms 18420 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 11604 KB Output is correct
2 Correct 410 ms 15920 KB Output is correct
3 Correct 380 ms 21328 KB Output is correct
4 Correct 463 ms 24968 KB Output is correct
5 Correct 416 ms 20188 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 11524 KB Output is correct
2 Correct 389 ms 11436 KB Output is correct
3 Correct 364 ms 19620 KB Output is correct
4 Correct 506 ms 24668 KB Output is correct
5 Correct 427 ms 21324 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 13008 KB Output is correct
2 Correct 465 ms 17208 KB Output is correct
3 Correct 437 ms 24480 KB Output is correct
4 Correct 544 ms 28496 KB Output is correct
5 Correct 497 ms 24004 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 13232 KB Output is correct
2 Correct 411 ms 13220 KB Output is correct
3 Correct 359 ms 22376 KB Output is correct
4 Correct 547 ms 28324 KB Output is correct
5 Correct 496 ms 24380 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 16212 KB Output is correct
2 Correct 558 ms 20544 KB Output is correct
3 Correct 560 ms 30432 KB Output is correct
4 Correct 666 ms 35264 KB Output is correct
5 Correct 614 ms 29496 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 16244 KB Output is correct
2 Correct 511 ms 16592 KB Output is correct
3 Correct 454 ms 28264 KB Output is correct
4 Correct 672 ms 35324 KB Output is correct
5 Correct 611 ms 30660 KB Output is correct