#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const long double eps = 1e-9;
const long double INF = 1e18;
const int MAXN = (int) 1e6;
struct Point {
long double x, y;
}pts[MAXN + 1];
inline long double dist(Point a, Point b) {
return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
struct Data {
long double l, r;
int id;
};
vector <Data> stk;
inline bool eq(long double a, long double b) {
return fabs(a - b) < eps;
}
long double L;
inline bool ok(long double &l, long double &r, Point b) {
Point a = pts[stk.back().id];
if(eq(a.x, b.x)) {
return 0;
}
long double x = 1.0 * (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * (b.x - a.x));
if(x > L) {
return 0;
}
if(dist(b, {stk.back().l, 0}) - dist(a, {stk.back().l, 0}) < 0) {
l = stk.back().l;
r = L;
return 1;
}
if(x - stk.back().l > 0) {
stk.back().r = x;
l = x;
r = L;
return 0;
}
l = stk.back().l;
r = L;
return 1;
}
int main() {
//ifstream cin("B.in");
//ofstream cout("B.out");
int i, n;
ios::sync_with_stdio(false);
cin >> n >> L;
for(i = 1; i <= n; i++) {
cin >> pts[i].x >> pts[i].y;
}
stk.push_back({0, L, 1});
for(i = 2; i <= n; i++) {
long double l = INF, r = -INF;
while(!stk.empty()) {
if(ok(l, r, pts[i])) {
stk.pop_back();
}
else {
break;
}
}
if(r - l > 0) {
stk.push_back({l, r, i});
}
}
long double ans = 0;
for(auto it : stk) {
ans = max(ans, dist(pts[it.id], {it.l, 0}));
ans = max(ans, dist(pts[it.id], {it.r, 0}));
}
cout << fixed << setprecision(20) << ans;
//cin.close();
//cout.close();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
4 |
Correct |
2 ms |
452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
684 KB |
Output is correct |
2 |
Correct |
5 ms |
856 KB |
Output is correct |
3 |
Correct |
4 ms |
856 KB |
Output is correct |
4 |
Correct |
5 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
1228 KB |
Output is correct |
2 |
Correct |
6 ms |
1288 KB |
Output is correct |
3 |
Correct |
6 ms |
1288 KB |
Output is correct |
4 |
Correct |
6 ms |
1328 KB |
Output is correct |
5 |
Incorrect |
5 ms |
1328 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
4644 KB |
Output is correct |
2 |
Correct |
54 ms |
5532 KB |
Output is correct |
3 |
Correct |
40 ms |
5532 KB |
Output is correct |
4 |
Correct |
59 ms |
7168 KB |
Output is correct |
5 |
Incorrect |
29 ms |
7168 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
46 ms |
8460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
15708 KB |
Output is correct |
2 |
Correct |
57 ms |
15708 KB |
Output is correct |
3 |
Correct |
57 ms |
15708 KB |
Output is correct |
4 |
Correct |
95 ms |
15708 KB |
Output is correct |
5 |
Correct |
85 ms |
15708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
16460 KB |
Output is correct |
2 |
Correct |
74 ms |
17692 KB |
Output is correct |
3 |
Correct |
67 ms |
19296 KB |
Output is correct |
4 |
Correct |
81 ms |
20668 KB |
Output is correct |
5 |
Correct |
64 ms |
21956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
25096 KB |
Output is correct |
2 |
Correct |
69 ms |
25096 KB |
Output is correct |
3 |
Correct |
61 ms |
26456 KB |
Output is correct |
4 |
Correct |
88 ms |
27936 KB |
Output is correct |
5 |
Correct |
65 ms |
29148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
332 ms |
70820 KB |
Output is correct |
2 |
Correct |
383 ms |
70820 KB |
Output is correct |
3 |
Correct |
343 ms |
70820 KB |
Output is correct |
4 |
Correct |
403 ms |
70820 KB |
Output is correct |
5 |
Correct |
332 ms |
70820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
397 ms |
70820 KB |
Output is correct |
2 |
Correct |
392 ms |
70820 KB |
Output is correct |
3 |
Correct |
314 ms |
70820 KB |
Output is correct |
4 |
Correct |
382 ms |
70820 KB |
Output is correct |
5 |
Correct |
338 ms |
70820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
458 ms |
99464 KB |
Output is correct |
2 |
Correct |
454 ms |
99464 KB |
Output is correct |
3 |
Correct |
439 ms |
99464 KB |
Output is correct |
4 |
Correct |
525 ms |
99464 KB |
Output is correct |
5 |
Correct |
395 ms |
99464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
454 ms |
99464 KB |
Output is correct |
2 |
Correct |
410 ms |
99464 KB |
Output is correct |
3 |
Correct |
364 ms |
99464 KB |
Output is correct |
4 |
Correct |
454 ms |
99464 KB |
Output is correct |
5 |
Correct |
400 ms |
99464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
487 ms |
123148 KB |
Output is correct |
2 |
Correct |
540 ms |
123148 KB |
Output is correct |
3 |
Correct |
578 ms |
123148 KB |
Output is correct |
4 |
Correct |
559 ms |
123148 KB |
Output is correct |
5 |
Correct |
517 ms |
123148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
545 ms |
123148 KB |
Output is correct |
2 |
Correct |
523 ms |
128316 KB |
Output is correct |
3 |
Runtime error |
496 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
647 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
630 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
702 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
824 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |