#include "bits/stdc++.h" #include <type_traits> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization("unroll-loops") // ============ Macros starts here ============ int recur_depth = 0; #ifdef DEBUG #define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;} #else #define dbg(x) #endif // DEBUG template<typename Ostream, typename Cont> typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) { os << "{"; for (auto& x : v) { os << x << ", "; } return os << "}"; } template<typename Ostream, typename ...Ts> Ostream& operator<<(Ostream& os, const pair<Ts...>& p) { return os << "{" << p.first << ", " << p.second << "}"; } #define readFast \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #ifdef LOCAL #define read() ifstream fin("date.in.txt") #else #define read() readFast #endif // LOCAL // ============ Macros ends here ============ #define fin cin #define ll long long #define sz(x) (int)(x).size() #define all(v) v.begin(), v.end() #define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n") #define LSB(x) (x & (-x)) #define test cout << "WORKS\n"; vector<long double> a, r; long double rb; bool intersect(int x, int y) { rb = (a[y] - a[x]) * (a[y] - a[x]) / (4 * r[x]); dbg(rb); dbg(rb - r[y] < 0.001); return rb - r[y] < 0.001; } int main() { read(); int n; fin >> n; a.resize(n); r.resize(n); for (int i = 0; i < n; ++i) { fin >> a[i] >> r[i]; } stack<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && intersect(stk.top(), i)) { r[i] = rb; stk.pop(); } stk.push(i); cout << fixed << setprecision(3) << r[i] << '\n'; } return 0; } /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! * test the solution with the given example * int overflow, array bounds, matrix bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH ~Benq~*/