#include <bits/stdc++.h>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
double L;
std::cin >> n >> L;
//std::vector<std::vector<int>> p(n, std::vector<int>(2, 0));
std::vector<std::vector<int>> p;
for (int i = 0; i < n; ++i) {
int x, y;
std::cin >> x >> y;
y = abs(y);
if (i == 0 || p[p.size() - 1][0] != x)
p.push_back({x, y});
else if (p[p.size() - 1][0] == x)
p[p.size() - 1][1] = std::min(p[p.size() - 1][1], y);
//std::cin >> p[i][0] >> p[i][1];
//p[i][1] = abs(p[i][1]);
}
n = p.size();
double d1 = sqrt(p[0][0] * p[0][0] + p[0][1] * p[0][1]);
double d2 = sqrt((p[0][0] - L) * (p[0][0] - L) + p[0][1] * p[0][1]);
double lo = 0, hi = std::max(d1, d2);
while(hi - lo > 1e-4) {
double mi = (lo + hi) / 2;
std::vector<std::vector<double>> u;
for (int i = 0; i < n; ++i) {
double h = p[i][1];
if (h > mi)
continue;
double lf = p[i][0] - sqrt(mi * mi - h * h);
double rt = p[i][0] + sqrt(mi * mi - h * h);
if (rt < 0.0 || lf > L)
continue;
lf = std::max(lf, 0.0);
rt = std::min(rt, L);
u.push_back({lf, rt});
}
sort(u.begin(), u.end());
double lf, rt;
lf = rt = -1;
bool ok = true;
for (int i = 0; i < u.size() && ok; ++i) {
if (i == 0) {
lf = u[i][0];
rt = u[i][1];
}
else {
if (u[i][0] > rt)
ok = false;
rt = std::max(rt, u[i][1]);
}
}
if (lf != 0 && rt != L)
ok = false;
if (ok) {
hi = mi;
}
else {
lo = mi;
}
}
std::cout << lo << "\n";
return 0;
}
Compilation message
mobile.cpp: In function 'int main()':
mobile.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < u.size() && ok; ++i) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
7 ms |
640 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
588 KB |
Output is correct |
2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
588 KB |
Output is correct |
2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
856 KB |
Output is correct |
2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
24 ms |
5340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
808 KB |
Output is correct |
2 |
Correct |
36 ms |
4788 KB |
Output is correct |
3 |
Incorrect |
53 ms |
7548 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
389 ms |
11232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
2820 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
278 ms |
11996 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1088 ms |
55108 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
121 ms |
1464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1082 ms |
76428 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
162 ms |
588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1098 ms |
87292 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
164 ms |
656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1092 ms |
98332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
186 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1098 ms |
109856 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
233 ms |
704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |