oj.uz

Submission #768919

# Submission time Handle Problem Language Result Execution time Memory
768919 2023-06-28T21:50:35 Z orcslop Mobile (BOI12_mobile) C++17
0 / 100
 670 ms 48148 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(n); 
    for(int i = 0; i < n; i++){
        intervals[i].first = max(v[i].first - sqrt(rad * rad - v[i].second * v[i].second), (double)0); 
        intervals[i].second = min(v[i].first  + sqrt(rad * rad - v[i].second * v[i].second), l); 
    }
    // sort(intervals.begin(), intervals.end()); 
    if(intervals[0].first != 0 || intervals[n-1].second != l) return false; 
    for(int i = 0; i < n-1; i++){
        if(intervals[i].second < intervals[i + 1].first) return false; 
    }
    return true; 
}

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 3516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3696 KB Output is correct
2 Incorrect 60 ms 4032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 4972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 20252 KB Output is correct
2 Correct 327 ms 23668 KB Output is correct
3 Correct 305 ms 23200 KB Output is correct
4 Incorrect 303 ms 25548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 24180 KB Output is correct
2 Incorrect 300 ms 22520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 24272 KB Output is correct
2 Incorrect 404 ms 28460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 28976 KB Output is correct
2 Incorrect 321 ms 27036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 28276 KB Output is correct
2 Incorrect 473 ms 33320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 33772 KB Output is correct
2 Incorrect 413 ms 31500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 32360 KB Output is correct
2 Incorrect 513 ms 37780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 38560 KB Output is correct
2 Incorrect 506 ms 36040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 40308 KB Output is correct
2 Incorrect 654 ms 47164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 48148 KB Output is correct
2 Incorrect 601 ms 44904 KB Output isn't correct
3 Halted 0 ms 0 KB -