Задача №114317. Воздушные шарики
Организаторы CEOI 2011 собираются устроить вечеринку с кучей воздушных шариков. Всего будет \(n\) шариков (они все имеют форму идеального шара), и они будут лежать на одной линии на полу.
Шарики ещё не надуты, и каждый из них изначально имеет нулевой радиус. Ещё, \(i\)-й шар прикреплён к полу в позиции \(x_i\). Они будут надуваться последовательно, слева направо. Когда какой-то шарик надувается, его радиус непрерывно увеличивается, пока не достигнет верхней границы своего размера, \(r_i\), либо же не каснётся одного из уже надутых.
Картинка 1: Шары из примера, после надувания.
Организваторы хотели бы оценить, сколько воздуха понадобится для надувания. Найдите, пожалуйста, итоговый радиус каждого шара.
В первой строке входных данных содержится целое число \(n\) (\(1\le n\le 200 000\)) – количество шаров.
Следующие \(n\) описывают шары. \(i\)-я из них содержит два целых числа \(x_i\) и \(r_i\) (\(0\le x_i\le 10^9\)), \(1\le r_i\le 10^9\)). Последовательность \(x_i\) строго возрастает.
Выведите \(n\) строк, в \(i\)-й строке должно быть единственное целое число – радиус \(i\)-го шара после надувания. Ваш ответ будет считаться верным, если он отличается от правильного не больше, чем на 0.001 в каждом числе.
1. (40 баллов) \(n\le 2000\).
2. (60 баллов) \(n\le 200000\).
3 0 9 8 1 13 7
9.000 1.000 4.694