시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 14 4 30.769%

문제

CEOI 2011 준비를 끝내니 파티를 열고 싶어졌다. 사실 파티보다는 풍선이 불고 싶다. n개의 풍선이 있고, 모두 완전한 공모양 풍선이며 바닥에 놓여져 있다.

풍선에는 아직 바람을 넣지 않아서, 각 풍선의 반지름은 0에서 시작한다. 덧붙여, i번째 풍선은 xi좌표에 착 붙어 있어 움직이지도 공중에 떠오르지도 않는다. 각 풍선은 왼쪽에서 오른쪽 순서대로 바람을 넣는다. 그 풍선은 반지름의 한계까지 (ri에 다다를 때까지) 점점 늘어나거나, 혹은 이전에 부풀린 다른 풍선과 맞닿을 때까지 늘어난다.

그림 1 : 예제의 풍선을 모두 부풀린 모습이다.

풍선을 모두 부풀리기 위해서 공기가 얼마나 필요한지 알고 싶다. 각 풍선들의 최종 반지름을 구하라.

입력

첫번째 줄에 풍선의 개수 n이 주어진다 (1 ≤ n ≤ 200 000).  이어지는 n개의 줄에는 풍선에 대한 정보가 주어진다. 

각 i번째 줄에는 xi와  ri 두 개의 정수가 주어진다. (풍선이 놓여 있는 x축 좌표 0 ≤ x≤ 109,  풍선의 반지름의 최대값 1 ≤ ri ≤ 109). 각 풍선들의 위치인 x좌표는 반드시 오른쪽으로만 나아간다.

출력

결과값은 반드시 n개의 줄로 출력되어야 하며, i번째 줄에는 정확히 i번째 풍선의 최종 반지름만 출력되어야 한다. 0.001 이하의 오차는 허용된다.

예제 입력

3
0 9
8 1
13 7

예제 출력

9.000
1.000
4.694

힌트

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2011 1번

  • 문제를 번역한 사람: pty115