시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 106 29 13 27.660%

문제

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 이하의 오차는 허용된다.

예제 입력 1

3
0 9
8 1
13 7

예제 출력 1

9.000
1.000
4.694
W3sicHJvYmxlbV9pZCI6IjMzMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ2OGNcdWFjMDAgXHViMDVkXHViMDk4XHVhY2UwIFx1YjA5YyBcdWI0YTQgXHViZTcwXHViZTYwXHViZTcwIiwiZGVzY3JpcHRpb24iOiI8cD5DRU9JIDIwMTEgXHVjOTAwXHViZTQ0XHViOTdjIFx1YjA1ZFx1YjBiNFx1YjJjOCZuYnNwO1x1ZDMwY1x1ZDJmMFx1Yjk3YyBcdWM1ZjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWMwYWNcdWMyZTQgXHVkMzBjXHVkMmYwXHViY2Y0XHViMmU0XHViMjk0IFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWJkODhcdWFjZTAgXHVjMmY2XHViMmU0LiBuXHVhYzFjXHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjQ1MCBcdWM2NDRcdWM4MDRcdWQ1NWMgXHVhY2Y1XHViYWE4XHVjNTkxJm5ic3A7XHVkNDhkXHVjMTIwXHVjNzc0XHViYTcwIFx1YmMxNFx1YjJlNVx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM4MzgmbmJzcDtcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDQ4ZFx1YzEyMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWM5YzEgXHViYzE0XHViNzhjXHVjNzQ0IFx1YjEyM1x1YzljMCBcdWM1NGFcdWM1NDRcdWMxMWMsIFx1YWMwMSBcdWQ0OGRcdWMxMjBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQwIDBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWIzNjdcdWJkOTlcdWM1ZWMsIGlcdWJjODhcdWM5ZjggXHVkNDhkXHVjMTIwXHVjNzQwJm5ic3A7eDxzdWI+aTxcL3N1Yj5cdWM4OGNcdWQ0NWNcdWM1ZDAmbmJzcDtcdWNjMjkgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YzViNCZuYnNwO1x1YzZjMFx1YzljMVx1Yzc3NFx1YzljMFx1YjNjNCBcdWFjZjVcdWM5MTFcdWM1ZDAgXHViNWEwXHVjNjI0XHViOTc0XHVjOWMwXHViM2M0IFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCZuYnNwO1x1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmMxNFx1Yjc4Y1x1Yzc0NCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1YWRmOCBcdWQ0OGRcdWMxMjBcdWM3NDAgXHViYzE4XHVjOWMwXHViOTg0XHVjNzU4Jm5ic3A7XHVkNTVjXHVhY2M0XHVhZTRjXHVjOWMwIChyPHN1Yj5pPFwvc3ViPlx1YzVkMCBcdWIyZTRcdWIyZTRcdWI5N2MgXHViNTRjXHVhZTRjXHVjOWMwKSBcdWM4MTBcdWM4MTAgXHViMjk4XHVjNWI0XHViMDk4XHVhYzcwXHViMDk4LCBcdWQ2MzlcdWM3NDAgXHVjNzc0XHVjODA0XHVjNWQwIFx1YmQ4MFx1ZDQ4MFx1YjliMCBcdWIyZTRcdWI5NzggXHVkNDhkXHVjMTIwXHVhY2ZjIFx1YjlkZVx1YjJmZlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHViMjk4XHVjNWI0XHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8zMzA3XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzMXB4OyBvcGFjaXR5OjAuOTsgdGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjM4NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1YWRmOFx1YjliYyAxIDogXHVjNjA4XHVjODFjXHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViZDgwXHVkNDgwXHViOWIwIFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJkODBcdWQ0ODBcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjJm5ic3A7XHVhY2Y1XHVhZTMwXHVhYzAwIFx1YzViY1x1YjljOFx1YjA5OCBcdWQ1NDRcdWM2OTRcdWQ1NWNcdWM5YzAgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVhYzAxIFx1ZDQ4ZFx1YzEyMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWM4ODUgXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOCZuYnNwO25cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgbiAmbGU7IDIwMCAwMDApLiAmbmJzcDtcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjMDEgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDt4PHN1Yj5pPFwvc3ViPlx1YzY0MCZuYnNwOyZuYnNwO3I8c3ViPmk8XC9zdWI+IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoXHVkNDhkXHVjMTIwXHVjNzc0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyOTQgeFx1Y2Q5NSBcdWM4OGNcdWQ0NWMmbmJzcDswICZsZTsgeDxzdWI+aSZuYnNwOzxcL3N1Yj4mbGU7IDEwPHN1cD45PFwvc3VwPiwgJm5ic3A7XHVkNDhkXHVjMTIwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTImbmJzcDsxICZsZTsgcjxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwPHN1cD45PFwvc3VwPikuIFx1YWMwMSBcdWQ0OGRcdWMxMjBcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzc4IHhcdWM4OGNcdWQ0NWNcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1Y1x1YjljYyBcdWIwOThcdWM1NDRcdWFjMDRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhY2IwXHVhY2ZjXHVhYzEyXHVjNzQwIFx1YmMxOFx1YjRkY1x1YzJkYyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggaVx1YmM4OFx1YzlmOCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVjZDVjXHVjODg1IFx1YmMxOFx1YzljMFx1Yjk4NFx1YjljYyBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzAuMDAxIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzMDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWxsb29ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG9yZ2FuaXplcnMgb2YgQ0VPSSAyMDExIGFyZSBwbGFubmluZyB0byBob2xkIGEgcGFydHkgd2l0aCBsb3RzIG9mIGJhbGxvb25zLiBUaGVyZSB3aWxsIGJlIG4gYmFsbG9vbnMsIGFsbCBzcGhlcmUtc2hhcGVkIGFuZCBseWluZyBpbiBhIGxpbmUgb24gdGhlIGZsb29yLjxcL3A+XHJcblxyXG48cD5UaGUgYmFsbG9vbnMgYXJlIHlldCB0byBiZSBpbmZsYXRlZCwgYW5kIGVhY2ggb2YgdGhlbSBpbml0aWFsbHkgaGFzIHplcm8gcmFkaXVzLiBBZGRpdGlvbmFsbHksIHRoZSBpLXRoIGJhbGxvb24gaXMgcGVybWFuZW50bHkgYXR0YWNoZWQgdG8gdGhlIGZsb29yIGF0IGNvb3JkaW5hdGUgeDxzdWI+aTxcL3N1Yj4uIFRoZXkgYXJlIGdvaW5nIHRvIGJlIGluZmxhdGVkIHNlcXVlbnRpYWxseSwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBXaGVuIGEgYmFsbG9vbiBpcyBpbmZsYXRlZCwgaXRzIHJhZGl1cyBpcyBpbmNyZWFzZWQgY29udGludW91c2x5IHVudGlsIGl0IHJlYWNoZXMgdGhlIHVwcGVyIGJvdW5kIGZvciB0aGUgYmFsbG9vbiwgcjxzdWI+aTxcL3N1Yj4sIG9yIHRoZSBiYWxsb29uIHRvdWNoZXMgb25lIG9mIHRoZSBwcmV2aW91c2x5IGluZmxhdGVkIGJhbGxvb25zLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8zMzA3XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzMXB4OyB3aWR0aDozODRweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMTogVGhlIGJhbGxvb25zIGZyb20gdGhlIGV4YW1wbGUgdGVzdCwgYWZ0ZXIgYmVpbmcgZnVsbHkgaW5mbGF0ZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBvcmdhbml6ZXJzIHdvdWxkIGxpa2UgdG8gZXN0aW1hdGUgaG93IG11Y2ggYWlyIHdpbGwgYmUgbmVlZGVkIHRvIGluZmxhdGUgYWxsIHRoZSBiYWxsb29ucy4gWW91IGFyZSB0byBmaW5kIHRoZSBmaW5hbCByYWRpdXMgZm9yIGVhY2ggYmFsbG9vbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDIwMCAwMDApICZtZGFzaDsgdGhlIG51bWJlciBvZiBiYWxsb29ucy4gVGhlIG5leHQgbiBsaW5lcyBkZXNjcmliZSB0aGUgYmFsbG9vbnMuIFRoZSBpLXRoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiBhbmQgcjxzdWI+aTxcL3N1Yj4gKDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgYmFsbG9vbnMgYXJlIGdpdmVuIGluIGEgc3RyaWN0bHkgaW5jcmVhc2luZyBvcmRlciBvZiB0aGUgeCBjb29yZGluYXRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGV4YWN0bHkgbiBsaW5lcywgd2l0aCB0aGUgaS10aCBsaW5lIGNvbnRhaW5pbmcgZXhhY3RseSBvbmUgbnVtYmVyICZtZGFzaDsgdGhlIHJhZGl1cyBvZiB0aGUgaS10aCBiYWxsb29uIGFmdGVyIGluZmxhdGluZy4gWW91ciBhbnN3ZXIgd2lsbCBiZSBhY2NlcHRlZCBpZiBpdCBkaWZmZXJzIGZyb20gdGhlIGNvcnJlY3Qgb25lIGJ5IG5vIG1vcmUgdGhhbiAwLjAwMSBmb3IgZWFjaCBudW1iZXIgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: pty115