#include <bits/stdc++.h>
#define int int64_t
#define f first
#define s second
#define mp make_pair
using namespace std;
bool check(double r, int L, const vector<array<int, 2>>& stations)
{
set<pair<double, double>> intervals;
for (const array<int, 2>& station : stations)
{
double diff_sqrd = r * r - station[1] * station[1];
if (diff_sqrd < 0)
continue;
double diff = sqrt(diff_sqrd);
double _l = station[0] - diff, _r = station[0] + diff;
if (_l > L || _r < 0)
continue;
intervals.insert(mp(_l, _r));
}
if (intervals.begin()->f > 0)
return false;
double last = (*intervals.begin()).s;
for (auto it = intervals.begin(); it != intervals.end() && last < L && it->f <= last; it++)
{
last = max(last, it->s);
}
return last >= L;
}
constexpr static int PRECISION = 1e5;
int32_t main()
{
int N, L;
cin >> N >> L;
vector<array<int, 2>> stations(N);
for (int i = 0; i < N; i++)
for (int j = 0; j < 2; j++)
cin >> stations[i][j];
double l = 0, r = 4e9;
while (r - l > 0.001)
{
double m = (r+l)*0.5;
if (check(m, L, stations))
r = m;
else
l = m;
}
cout << r << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
468 KB |
Output is correct |
2 |
Correct |
12 ms |
508 KB |
Output is correct |
3 |
Correct |
7 ms |
448 KB |
Output is correct |
4 |
Incorrect |
6 ms |
460 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
724 KB |
Output is correct |
2 |
Incorrect |
28 ms |
688 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
692 KB |
Output is correct |
2 |
Incorrect |
27 ms |
596 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
684 KB |
Output is correct |
2 |
Incorrect |
28 ms |
596 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
6068 KB |
Output is correct |
2 |
Incorrect |
544 ms |
6224 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
311 ms |
6388 KB |
Output is correct |
2 |
Correct |
233 ms |
5756 KB |
Output is correct |
3 |
Incorrect |
250 ms |
6552 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
696 ms |
7116 KB |
Output is correct |
2 |
Incorrect |
611 ms |
6708 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
617 ms |
8012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
363 ms |
8000 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1099 ms |
39368 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1089 ms |
39420 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1082 ms |
47264 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
47240 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1077 ms |
55036 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1100 ms |
55068 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1086 ms |
62896 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
62864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1094 ms |
78568 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1094 ms |
78532 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |