#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const double eps = 1e-9;
const double INF = 1e18;
const int MAXN = (int) 1e6;
struct Point {
double x, y;
}pts[MAXN + 1];
inline 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 {
double l, r;
int id;
};
vector <Data> stk;
inline bool eq(double a, double b) {
return fabs(a - b) < eps;
}
double L;
inline bool ok(double &l, double &r, Point b) {
Point a = pts[stk.back().id];
if(eq(a.x, b.x)) {
return 0;
}
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;
}
x = max(x, (double) 0.0);
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.tie(0), cout.tie(0);
cin >> n >> L;
int sz = 0;
for(i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
y = fabs(y);
if(sz > 0 && eq(x, pts[sz].x)) {
pts[sz].y = min(pts[sz].y, y);
}
else {
pts[++sz] = {x, y};
}
}
n = sz;
stk.push_back({0, L, 1});
for(i = 2; i <= n; i++) {
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});
}
}
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
2 ms |
420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
472 KB |
Output is correct |
2 |
Correct |
2 ms |
560 KB |
Output is correct |
3 |
Correct |
2 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
612 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
4 ms |
796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
796 KB |
Output is correct |
2 |
Correct |
5 ms |
844 KB |
Output is correct |
3 |
Correct |
5 ms |
844 KB |
Output is correct |
4 |
Correct |
5 ms |
988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
988 KB |
Output is correct |
2 |
Correct |
5 ms |
1104 KB |
Output is correct |
3 |
Correct |
4 ms |
1104 KB |
Output is correct |
4 |
Correct |
5 ms |
1352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1352 KB |
Output is correct |
2 |
Correct |
5 ms |
1376 KB |
Output is correct |
3 |
Correct |
4 ms |
1376 KB |
Output is correct |
4 |
Correct |
5 ms |
1500 KB |
Output is correct |
5 |
Correct |
5 ms |
1500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
3416 KB |
Output is correct |
2 |
Correct |
54 ms |
4328 KB |
Output is correct |
3 |
Correct |
39 ms |
4896 KB |
Output is correct |
4 |
Correct |
60 ms |
6236 KB |
Output is correct |
5 |
Correct |
30 ms |
6236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
6352 KB |
Output is correct |
2 |
Correct |
49 ms |
7548 KB |
Output is correct |
3 |
Correct |
51 ms |
9144 KB |
Output is correct |
4 |
Correct |
57 ms |
10456 KB |
Output is correct |
5 |
Correct |
60 ms |
12132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
16020 KB |
Output is correct |
2 |
Correct |
60 ms |
16020 KB |
Output is correct |
3 |
Correct |
51 ms |
16320 KB |
Output is correct |
4 |
Correct |
90 ms |
16320 KB |
Output is correct |
5 |
Correct |
54 ms |
16320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
16320 KB |
Output is correct |
2 |
Correct |
64 ms |
16320 KB |
Output is correct |
3 |
Correct |
59 ms |
16320 KB |
Output is correct |
4 |
Correct |
75 ms |
16320 KB |
Output is correct |
5 |
Correct |
65 ms |
16320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
16392 KB |
Output is correct |
2 |
Correct |
73 ms |
16392 KB |
Output is correct |
3 |
Correct |
55 ms |
16392 KB |
Output is correct |
4 |
Correct |
84 ms |
16392 KB |
Output is correct |
5 |
Correct |
72 ms |
16392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
34228 KB |
Output is correct |
2 |
Correct |
333 ms |
34228 KB |
Output is correct |
3 |
Correct |
335 ms |
34228 KB |
Output is correct |
4 |
Correct |
375 ms |
34228 KB |
Output is correct |
5 |
Correct |
304 ms |
34228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
34228 KB |
Output is correct |
2 |
Correct |
306 ms |
34228 KB |
Output is correct |
3 |
Correct |
310 ms |
34228 KB |
Output is correct |
4 |
Correct |
363 ms |
34228 KB |
Output is correct |
5 |
Correct |
316 ms |
34228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
48064 KB |
Output is correct |
2 |
Correct |
382 ms |
48064 KB |
Output is correct |
3 |
Correct |
360 ms |
48064 KB |
Output is correct |
4 |
Correct |
486 ms |
48064 KB |
Output is correct |
5 |
Correct |
377 ms |
48064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
414 ms |
48064 KB |
Output is correct |
2 |
Correct |
366 ms |
48064 KB |
Output is correct |
3 |
Correct |
318 ms |
48064 KB |
Output is correct |
4 |
Correct |
450 ms |
48064 KB |
Output is correct |
5 |
Correct |
366 ms |
48064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
392 ms |
49708 KB |
Output is correct |
2 |
Correct |
446 ms |
49708 KB |
Output is correct |
3 |
Correct |
439 ms |
49708 KB |
Output is correct |
4 |
Correct |
599 ms |
49708 KB |
Output is correct |
5 |
Correct |
406 ms |
49708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
507 ms |
49708 KB |
Output is correct |
2 |
Correct |
460 ms |
49708 KB |
Output is correct |
3 |
Correct |
418 ms |
49708 KB |
Output is correct |
4 |
Correct |
510 ms |
49708 KB |
Output is correct |
5 |
Correct |
515 ms |
49708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
443 ms |
51116 KB |
Output is correct |
2 |
Correct |
544 ms |
51116 KB |
Output is correct |
3 |
Correct |
517 ms |
51116 KB |
Output is correct |
4 |
Correct |
619 ms |
51116 KB |
Output is correct |
5 |
Correct |
480 ms |
51116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
526 ms |
51116 KB |
Output is correct |
2 |
Correct |
512 ms |
51116 KB |
Output is correct |
3 |
Correct |
491 ms |
51116 KB |
Output is correct |
4 |
Correct |
640 ms |
51116 KB |
Output is correct |
5 |
Correct |
526 ms |
51116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
578 ms |
54268 KB |
Output is correct |
2 |
Correct |
701 ms |
54268 KB |
Output is correct |
3 |
Correct |
654 ms |
54268 KB |
Output is correct |
4 |
Correct |
756 ms |
54268 KB |
Output is correct |
5 |
Correct |
627 ms |
54268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
761 ms |
54268 KB |
Output is correct |
2 |
Correct |
615 ms |
54268 KB |
Output is correct |
3 |
Correct |
597 ms |
54268 KB |
Output is correct |
4 |
Correct |
716 ms |
61308 KB |
Output is correct |
5 |
Correct |
688 ms |
73652 KB |
Output is correct |