#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, x[N], r[N];
long double ans[N];
long double calc(int i, int j){
long double lo = 0, hi = r[j];
long double dx = abs(x[j] - x[i]);
for(int t = 0; t < 100; t++){
long double mid = (lo + hi) / 2;
long double dy = abs(mid - ans[i]);
if(dx * dx + dy * dy >= (mid + ans[i]) * (mid + ans[i])){
lo = mid;
} else{
hi = mid;
}
}
return lo;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x[i] >> r[i];
ans[i] = r[i];
}
stack<int> st;
for(int i = 1; i < n; i++){
long double reach = r[i];
if(st.size()) reach = min(reach, calc(st.top(), i));
ans[i] = reach;
while(st.size() && calc(st.top(), i + 1) > calc(i, i + 1)) st.pop();
st.push(i);
}
while(st.size()){
ans[n] = min(ans[n], calc(st.top(), n));
st.pop();
}
for(int i = 1; i <= n; i++)
cout << setprecision(3) << fixed << ans[i] << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
5th numbers differ - expected: '17.1630000000', found: '99.0000000000', error = '81.8370000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
504 KB |
2 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
336 KB |
3rd numbers differ - expected: '0.0420000000', found: '3.0000000000', error = '2.9580000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
336 KB |
114th numbers differ - expected: '39.0180000000', found: '56.0000000000', error = '16.9820000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
125 ms |
1360 KB |
196th numbers differ - expected: '100.7250000000', found: '111.0000000000', error = '10.2750000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
345 ms |
2616 KB |
13945th numbers differ - expected: '0.0140000000', found: '7.0000000000', error = '6.9860000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
628 ms |
5036 KB |
7236th numbers differ - expected: '0.0070000000', found: '7.0000000000', error = '6.9930000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
724 ms |
5640 KB |
4645th numbers differ - expected: '0.0260000000', found: '8.0000000000', error = '7.9740000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
956 ms |
7644 KB |
1730th numbers differ - expected: '5.6890000000', found: '6.8060000000', error = '1.1170000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1301 ms |
9296 KB |
2716th numbers differ - expected: '22.1690000000', found: '43.0000000000', error = '20.8310000000' |
2 |
Halted |
0 ms |
0 KB |
- |