Submission #466646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466646	2021-08-19T23:12:30 Z	bill_lin	Mobile (BOI12_mobile)	C++14	0 / 100	1000 ms	21132 KB

mobile

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
#define MOD 1000000007
#define INF 10000000

int n, l;

vector<pii> coords;

bool possible(ld curr) {
    ld right_bound = 0;
    for (int i = 0; i < n; i++) {
        ld left_most = coords[i].first - sqrt(curr * curr - (ld) coords[i].second * coords[i].second);
        if (left_most > right_bound) return true;
        right_bound = max(right_bound, coords[i].first + sqrt(curr * curr - (ld) coords[i].second * coords[i].second));
        
    }
    return right_bound < l;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
//    freopen("multimoo.in", "r", stdin);
//    freopen("multimoo.out", "w", stdout);
    
    cin >> n >> l;
    
    coords.resize(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        coords[i] = {x, y};
    }
    
    ld l = 0, r = 1e9;
    for (int iteration = 0; iteration <= 50; iteration++) {
        ld mp = (l + r) / 2;
        if (possible(mp)) {
            l = mp;
        } else r = mp;
    }
    
    cout.precision(10);
    cout << l << '\n';
    
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	1604 KB	Output is correct
2	Incorrect	36 ms	2108 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	12408 KB	Output is correct
2	Incorrect	783 ms	10820 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	10180 KB	Output is correct
2	Incorrect	253 ms	12160 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	11788 KB	Output is correct
2	Incorrect	296 ms	14036 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	17300 KB	Output is correct
2	Execution timed out	1077 ms	12908 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	456 ms	13464 KB	Output is correct
2	Incorrect	361 ms	16452 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	18084 KB	Output is correct
2	Execution timed out	1043 ms	13752 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	356 ms	15860 KB	Output is correct
2	Execution timed out	1091 ms	15172 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Submission #466646

Compilation message