대회가 끝나고 난 뒤 빰빠빰

시간 제한1초메모리 제한128 MB

요약

풍선들이 왼쪽부터 순서대로 부풀며 최대 반지름에 도달하거나 이전 풍선에 닿으면 멈출 때 각 풍선의 최종 반지름을 효율적으로 구하는 문제입니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 기하, 스택
정답자: 아직 제출이 없습니다

문제

CEOI 2011 준비를 마치고 나니 파티를 열고 싶어졌다. 사실 파티보다 풍선을 부는 일이 더 하고 싶다. 바닥에 완전한 공 모양의 풍선 $n$ 개가 놓여 있다.

아직 바람을 넣지 않아 각 풍선의 반지름은 $0$ 에서 시작한다. $i$ 번째 풍선은 $x_i$ 좌표에 고정되어 있어 움직이거나 공중에 떠오르지 않는다. 풍선은 왼쪽에서 오른쪽 순서대로 하나씩 바람을 넣는다. 각 풍선은 자신의 최대 반지름 $r_i$ 에 도달하거나, 먼저 부풀린 다른 풍선과 맞닿는 순간까지 점점 커진다.

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

모든 풍선의 최종 반지름을 구하여라.

입력

첫째 줄에 풍선의 개수 $n$ 이 주어진다 ( $1 \le n \le 200\,000$ ).

이어지는 $n$ 개의 줄 중 $i$ 번째 줄에는 두 정수 $x_i$ 와 $r_i$ 가 공백으로 구분되어 주어진다. $x_i$ 는 풍선이 놓인 $x$ 좌표이며 ( $0 \le x_i \le 10^9$ ), $r_i$ 는 그 풍선이 커질 수 있는 최대 반지름이다 ( $1 \le r_i \le 10^9$ ). 풍선은 왼쪽에서 오른쪽 순서로 주어지며 $x$ 좌표는 엄격히 증가한다. 즉 $x_1 < x_2 < \dots < x_n$ 이다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 풍선의 최종 반지름을 소수점 아래 셋째 자리까지 반올림하여 출력한다.

예제2

예제 1
입력
```
3
0 9
8 1
13 7
```
예상 출력
```
9.000
1.000
4.694
```
예제 2
입력
```
2
0 10
6 10
```
예상 출력
```
10.000
0.900
```