#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef pair<double,double> S;
S seg(pl a, double rad) {
if(a.second > rad) {return {a.second,a.second};}
double r = sqrt(rad*rad-a.second*a.second);
return {a.first-r,a.first+r};
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n,len;
cin >> n >> len;
vpl w;
for(int i=0;i<n;i++) {
ll a,b;
cin >> a >> b;
b = abs(b);
w.emplace_back(a,b);
}
double st = 0;
double ed = 4e9;
double ls = ed;
for(int iter=0;iter<45;iter++) {
double m = (st+ed)/2;
stack<S> sto;
bool poss = false;
for(int i=0;i<n;i++) {
if(poss) {break;}
if(m > w[i].second) {
S se = seg(w[i],m);
while(!sto.empty() && sto.top().second > se.first) {
se.first = min(se.first,sto.top().first);
se.second = max(se.second,sto.top().second);
sto.pop();
}
if(se.first <= 0 && se.second >= len) {
poss = true;
break;
}
sto.push(se);
}
}
if(poss) {
ls = m;
ed = m;
} else {
st = m;
}
}
cout << fixed << setprecision(7) << ls << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
2504 KB |
Output is correct |
2 |
Correct |
27 ms |
2456 KB |
Output is correct |
3 |
Correct |
14 ms |
1484 KB |
Output is correct |
4 |
Correct |
18 ms |
2504 KB |
Output is correct |
5 |
Correct |
9 ms |
1484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
2504 KB |
Output is correct |
2 |
Correct |
17 ms |
2504 KB |
Output is correct |
3 |
Correct |
18 ms |
2408 KB |
Output is correct |
4 |
Correct |
19 ms |
2504 KB |
Output is correct |
5 |
Correct |
26 ms |
2504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
2504 KB |
Output is correct |
2 |
Correct |
26 ms |
2476 KB |
Output is correct |
3 |
Correct |
21 ms |
2416 KB |
Output is correct |
4 |
Correct |
26 ms |
2460 KB |
Output is correct |
5 |
Correct |
18 ms |
2512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
2516 KB |
Output is correct |
2 |
Correct |
35 ms |
2436 KB |
Output is correct |
3 |
Correct |
26 ms |
2504 KB |
Output is correct |
4 |
Correct |
27 ms |
2476 KB |
Output is correct |
5 |
Correct |
21 ms |
2504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
2404 KB |
Output is correct |
2 |
Correct |
35 ms |
2488 KB |
Output is correct |
3 |
Correct |
27 ms |
2504 KB |
Output is correct |
4 |
Correct |
27 ms |
2472 KB |
Output is correct |
5 |
Correct |
21 ms |
2504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
215 ms |
8628 KB |
Output is correct |
2 |
Correct |
183 ms |
8612 KB |
Output is correct |
3 |
Correct |
136 ms |
8584 KB |
Output is correct |
4 |
Correct |
125 ms |
8644 KB |
Output is correct |
5 |
Correct |
108 ms |
8624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
218 ms |
8644 KB |
Output is correct |
2 |
Correct |
233 ms |
8636 KB |
Output is correct |
3 |
Correct |
126 ms |
8648 KB |
Output is correct |
4 |
Correct |
130 ms |
8608 KB |
Output is correct |
5 |
Correct |
114 ms |
8616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
268 ms |
16852 KB |
Output is correct |
2 |
Correct |
216 ms |
16804 KB |
Output is correct |
3 |
Correct |
181 ms |
16752 KB |
Output is correct |
4 |
Correct |
161 ms |
16816 KB |
Output is correct |
5 |
Correct |
132 ms |
16804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
261 ms |
16868 KB |
Output is correct |
2 |
Correct |
273 ms |
16936 KB |
Output is correct |
3 |
Correct |
161 ms |
16856 KB |
Output is correct |
4 |
Correct |
159 ms |
16848 KB |
Output is correct |
5 |
Correct |
138 ms |
16784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
304 ms |
16784 KB |
Output is correct |
2 |
Correct |
241 ms |
16740 KB |
Output is correct |
3 |
Correct |
231 ms |
16892 KB |
Output is correct |
4 |
Correct |
185 ms |
16836 KB |
Output is correct |
5 |
Correct |
149 ms |
16840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
286 ms |
16860 KB |
Output is correct |
2 |
Correct |
301 ms |
16768 KB |
Output is correct |
3 |
Correct |
187 ms |
16776 KB |
Output is correct |
4 |
Correct |
189 ms |
16860 KB |
Output is correct |
5 |
Correct |
157 ms |
16784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
344 ms |
16804 KB |
Output is correct |
2 |
Correct |
301 ms |
16804 KB |
Output is correct |
3 |
Correct |
219 ms |
16804 KB |
Output is correct |
4 |
Correct |
212 ms |
16804 KB |
Output is correct |
5 |
Correct |
178 ms |
16800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
330 ms |
16764 KB |
Output is correct |
2 |
Correct |
333 ms |
16756 KB |
Output is correct |
3 |
Correct |
201 ms |
16824 KB |
Output is correct |
4 |
Correct |
214 ms |
16880 KB |
Output is correct |
5 |
Correct |
181 ms |
16836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
445 ms |
16800 KB |
Output is correct |
2 |
Correct |
287 ms |
16804 KB |
Output is correct |
3 |
Correct |
336 ms |
16868 KB |
Output is correct |
4 |
Correct |
261 ms |
16800 KB |
Output is correct |
5 |
Correct |
217 ms |
16760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
445 ms |
16948 KB |
Output is correct |
2 |
Correct |
409 ms |
16804 KB |
Output is correct |
3 |
Correct |
276 ms |
16840 KB |
Output is correct |
4 |
Correct |
259 ms |
16856 KB |
Output is correct |
5 |
Correct |
226 ms |
16836 KB |
Output is correct |