CEOI 2011 day 1

bal.cpp

#include <bits/stdc++.h>

using Ldouble = long double;

using namespace std;

stack<pair<int, Ldouble>> balloons;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	int x, x1;
	Ldouble r, r1;
	
	cin>>n;
	
	while (n--)
	{
		cin>>x>>r;
		
		while (!balloons.empty())
		{
			tie(x1, r1) = balloons.top();
			
			r = min(r, Ldouble(x - x1) * (x - x1) / 4 / r1);
			
			if (r < r1) break;
			
			balloons.pop();
		}
		
		balloons.emplace(x, r);
		
		cout<<fixed<<setprecision(3)<<r<<'\n';
	}
}