#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
struct ball{
long double x,r;
};
ball a[200001];
long double res[200001];
int st[200001];
int to = 0;
void pu(int pos){
st[++to] = pos;
}
void po(){
to--;
}
int n;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i].x >> a[i].r;
res[1] = a[1].r;
pu(1);
for(int i = 2;i <= n;i++){
res[i] = a[i].r;
res[i] = min(res[i],(a[st[to]].x*a[st[to]].x - 2*a[i].x*a[st[to]].x + a[i].x*a[i].x)/(4*res[st[to]]));
while(to && res[i] >= res[st[to]]){
po();
res[i] = min(res[i],(a[st[to]].x*a[st[to]].x - 2*a[i].x*a[st[to]].x + a[i].x*a[i].x)/(4*res[st[to]]));
}
pu(i);
}
for(int i = 1;i <= n;i++){
cout << fixed << setprecision(3) << res[i] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |