oj.uz

Submission #1093055

# Submission time Handle Problem Language Result Execution time Memory
1093055 2024-09-25T18:52:47 Z TommasoUlian Mobile (BOI12_mobile) C++14
0 / 100
 784 ms 47624 KB 
#include <bits/stdc++.h>
#define PB push_back
#define MP makepair
#ifndef ONLINE_JUDGE
#define DEBUG(x) cout << #x << " = " << (x) << endl
#else
#define DEBUG(x)
#endif
#define FOR(n) for(int i = 0; i < (n); i++)
#define SORTA(v) sort((v).begin(), (v).end())
#define SORTD(v) sort((v).rbegin(), (v).rend())
#define PRINT(v) for(auto x: (v))cout << x << " "; cout << endl;
#define TWO(n) (1 << (n))
#define INPUT(v) for(auto &x : (v))cin >> x;
 
typedef long long ll;
 
using namespace std;
 
vector<pair<double,double>> torri;
ll n,L;
 
bool good(double r){
    queue<pair<double,double>> s;
    
    for(auto a:torri){
        double x = a.first, y = a.second;
        if (abs(y) <= r-10e-6)s.push({x-sqrt((r+y)*(r-y)),x+sqrt((r+y)*(r-y))});
       
    }
    double curr = 0;
    while(!s.empty()){
        if(curr >= L)return true;
        auto seg = s.front();
        s.pop();
        if(seg.first-10e-8 <= curr){
            curr = max(seg.second,curr);
        }
        else return false;
    }
    if(curr < L-10e-8)return false;
    return true;
}
 
void solve(){
    cin >> n >> L;
    torri = vector<pair<double,double>>(n);
    for(int i = 0; i < n; i++){
        cin >> torri[i].first >> torri[i].second;
 
    }
    double l = 1, r = 2e9;
    double ans = r;
    while(r-l >= 10e-7){
        double c = (r+l)/2;
        //cout << c << endl;
        if(good(c)){
            ans = min(ans,c);
            r = c;
        }
        else{
            l = c;
        }
 
    }
    
    cout << ans << endl;
    
}
 
int main(){
    cout << setprecision(18);
    ios::sync_with_stdio(false);

    solve();
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4068 KB Output is correct
2 Incorrect 59 ms 4392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 5332 KB Output is correct
2 Incorrect 70 ms 5204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 20796 KB Output is correct
2 Correct 350 ms 23884 KB Output is correct
3 Correct 337 ms 23244 KB Output is correct
4 Incorrect 204 ms 25452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 24280 KB Output is correct
2 Incorrect 366 ms 22848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 24728 KB Output is correct
2 Incorrect 417 ms 28744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 29144 KB Output is correct
2 Incorrect 462 ms 27588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 29028 KB Output is correct
2 Incorrect 517 ms 33528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 33988 KB Output is correct
2 Incorrect 529 ms 31400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 32620 KB Output is correct
2 Incorrect 584 ms 37576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 38108 KB Output is correct
2 Incorrect 568 ms 35980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 40688 KB Output is correct
2 Incorrect 765 ms 46596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 47624 KB Output is correct
2 Incorrect 721 ms 44384 KB Output isn't correct
3 Halted 0 ms 0 KB -