#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 1e6+5;
int n, m;
pair<long double, long double> p[N];
stack<pair<int, pair<long double, long double>>> s;
long double dis(int i, long double x)
{
long double y = 0;
return hypot((x-p[i].f), (y-p[i].s));
}
int main()
{
cin >> n >> m;
for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s;
for(int i=0; i<n; i++)
{
if(s.empty()) s.push({i, {0, m}});
else
{
auto t = s.top();
if(p[i].f == p[t.f].f || dis(t.f, t.s.s) < dis(i, t.s.s))
continue;
long double x;
while(!s.empty() && dis(s.top().f, s.top().s.f) >= dis(i, s.top().s.f)) s.pop();
if(s.empty())
{
s.push({i, {0, m}});
continue;
}
t = s.top();
if(dis(t.f, t.s.s) >= dis(i, t.s.s))
{
long double l = t.s.f, r = t.s.s;
for(int j=0; j<50; j++)
{
x = (l+r)/2;
if(dis(t.f, x) <= dis(i, x)) l = x;
else r = x;
}
/*
long double x1 = p[i].f, x2 = p[t.f].f;
long double y1 = p[i].s, y2 = p[t.f].s;
x = (x1*x1 - x2*x2 + y1*y1-y2*y2)/(2*x1-2*x2);
if(x <= t.s.f) continue;
*/
s.pop();
t.s.s = x;
s.push(t);
s.push({i, {x, m}});
}
else s.push({i, {t.s.s, m}});
}
}
long double ans = 0;
while(!s.empty())
{
auto t = s.top();
s.pop();
ans = max(ans, max(dis(t.f, t.s.f), dis(t.f, t.s.s)));
}
cout << fixed << setprecision(7) << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
25 ms |
504 KB |
Output is correct |
3 |
Correct |
9 ms |
632 KB |
Output is correct |
4 |
Correct |
12 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
632 KB |
Output is correct |
2 |
Correct |
25 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
552 KB |
Output is correct |
4 |
Correct |
13 ms |
516 KB |
Output is correct |
5 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
3576 KB |
Output is correct |
2 |
Correct |
134 ms |
3832 KB |
Output is correct |
3 |
Correct |
287 ms |
2680 KB |
Output is correct |
4 |
Correct |
145 ms |
3832 KB |
Output is correct |
5 |
Incorrect |
62 ms |
2296 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
116 ms |
3548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
614 ms |
8048 KB |
Output is correct |
2 |
Correct |
147 ms |
4088 KB |
Output is correct |
3 |
Correct |
377 ms |
5780 KB |
Output is correct |
4 |
Correct |
225 ms |
5368 KB |
Output is correct |
5 |
Correct |
136 ms |
3964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
4960 KB |
Output is correct |
2 |
Correct |
171 ms |
4892 KB |
Output is correct |
3 |
Correct |
189 ms |
4852 KB |
Output is correct |
4 |
Correct |
221 ms |
5572 KB |
Output is correct |
5 |
Correct |
169 ms |
4736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
416 ms |
6136 KB |
Output is correct |
2 |
Correct |
172 ms |
4924 KB |
Output is correct |
3 |
Correct |
188 ms |
4864 KB |
Output is correct |
4 |
Correct |
226 ms |
5372 KB |
Output is correct |
5 |
Correct |
182 ms |
4764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1073 ms |
24776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
927 ms |
24440 KB |
Output is correct |
2 |
Execution timed out |
1075 ms |
22912 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1065 ms |
27160 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1077 ms |
29176 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1073 ms |
30316 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1066 ms |
29276 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1066 ms |
33672 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1076 ms |
29944 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
37288 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1075 ms |
28844 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |