#include <cassert> #include <iomanip> #include <ios> #include <iostream> #include <map> #include <vector> using namespace std; using ld = long double; // 1/a * (x - b)^2 struct Quad { ld a; uint b; ld eval(uint x) const { assert(x >= b); ld dst = x - b; return (dst * dst) / a; } }; struct Bal { uint x, r; }; constexpr uint maxx = 1e9; uint find_intersect(const Quad &q, const map<uint, Quad> &quads) { if (quads.lower_bound(q.b) == quads.end()) return maxx; uint s = q.b, e = maxx; while (s < e) { const uint mid = (s + e + 1) / 2; const map<uint, Quad>::const_iterator competitor_it = quads.lower_bound(mid); assert(competitor_it != quads.end()); Quad competitior = competitor_it->second; if (q.eval(mid) < competitior.eval(mid)) { s = mid; } else { e = mid - 1; } } return s; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); uint n; cin >> n; vector<Bal> baloons(n); for (uint i = 0; i < n; i++) { cin >> baloons[i].x >> baloons[i].r; } map<uint, Quad> quads; vector<ld> rs(n); for (uint i = 0; i < n; i++) { Bal bal = baloons[i]; const map<uint, Quad>::const_iterator it = quads.lower_bound(bal.x); rs[i] = (it != quads.end() ? min(it->second.eval(bal.x), (ld)bal.r) : bal.r); Quad q(4 * rs[i], bal.x); uint intersect = find_intersect(q, quads); quads[intersect] = q; quads.erase(quads.begin(), quads.find(intersect)); } cout << fixed << setprecision(3); for (ld r : rs) { cout << r << '\n'; } }