시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 122 31 15 23.810%

문제

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+XHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJkODBcdWQ0ODBcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjJm5ic3A7XHVhY2Y1XHVhZTMwXHVhYzAwIFx1YzViY1x1YjljOFx1YjA5OCBcdWQ1NDRcdWM2OTRcdWQ1NWNcdWM5YzAgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVhYzAxIFx1ZDQ4ZFx1YzEyMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWM4ODUgXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTgmbmJzcDtuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IG4gJmxlOyAyMDAgMDAwKS4gJm5ic3A7XHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDQ4ZFx1YzEyMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhYzAxIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7eDxzdWI+aTxcL3N1Yj5cdWM2NDAmbmJzcDsmbmJzcDtyPHN1Yj5pPFwvc3ViPiBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMjk0IHhcdWNkOTUgXHVjODhjXHVkNDVjJm5ic3A7MCAmbGU7IHg8c3ViPmkmbmJzcDs8XC9zdWI+JmxlOyAxMDxzdXA+OTxcL3N1cD4sICZuYnNwO1x1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyJm5ic3A7MSAmbGU7IHI8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBcdWFjMDEgXHVkNDhkXHVjMTIwXHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc3OCB4XHVjODhjXHVkNDVjXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWNcdWI5Y2MgXHViMDk4XHVjNTQ0XHVhYzA0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWNiMFx1YWNmY1x1YWMxMlx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjZDljXHViODI1XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVkNjU1XHVkNzg4IGlcdWJjODhcdWM5ZjggXHVkNDhkXHVjMTIwXHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWJjMThcdWM5YzBcdWI5ODRcdWI5Y2MgXHVjZDljXHViODI1XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDswLjAwMSBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNjI0XHVjYzI4XHViMjk0IFx1ZDVjOFx1YzZhOVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsbG9vbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBvcmdhbml6ZXJzIG9mIENFT0kgMjAxMSBhcmUgcGxhbm5pbmcgdG8gaG9sZCBhIHBhcnR5IHdpdGggbG90cyBvZiBiYWxsb29ucy4gVGhlcmUgd2lsbCBiZSBuIGJhbGxvb25zLCBhbGwgc3BoZXJlLXNoYXBlZCBhbmQgbHlpbmcgaW4gYSBsaW5lIG9uIHRoZSBmbG9vci48XC9wPlxyXG5cclxuPHA+VGhlIGJhbGxvb25zIGFyZSB5ZXQgdG8gYmUgaW5mbGF0ZWQsIGFuZCBlYWNoIG9mIHRoZW0gaW5pdGlhbGx5IGhhcyB6ZXJvIHJhZGl1cy4gQWRkaXRpb25hbGx5LCB0aGUgaS10aCBiYWxsb29uIGlzIHBlcm1hbmVudGx5IGF0dGFjaGVkIHRvIHRoZSBmbG9vciBhdCBjb29yZGluYXRlIHg8c3ViPmk8XC9zdWI+LiBUaGV5IGFyZSBnb2luZyB0byBiZSBpbmZsYXRlZCBzZXF1ZW50aWFsbHksIGZyb20gbGVmdCB0byByaWdodC4gV2hlbiBhIGJhbGxvb24gaXMgaW5mbGF0ZWQsIGl0cyByYWRpdXMgaXMgaW5jcmVhc2VkIGNvbnRpbnVvdXNseSB1bnRpbCBpdCByZWFjaGVzIHRoZSB1cHBlciBib3VuZCBmb3IgdGhlIGJhbGxvb24sIHI8c3ViPmk8XC9zdWI+LCBvciB0aGUgYmFsbG9vbiB0b3VjaGVzIG9uZSBvZiB0aGUgcHJldmlvdXNseSBpbmZsYXRlZCBiYWxsb29ucy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMzMwN1wvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMzFweDsgd2lkdGg6Mzg0cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIDE6IFRoZSBiYWxsb29ucyBmcm9tIHRoZSBleGFtcGxlIHRlc3QsIGFmdGVyIGJlaW5nIGZ1bGx5IGluZmxhdGVkLjxcL3A+XHJcblxyXG48cD5UaGUgb3JnYW5pemVycyB3b3VsZCBsaWtlIHRvIGVzdGltYXRlIGhvdyBtdWNoIGFpciB3aWxsIGJlIG5lZWRlZCB0byBpbmZsYXRlIGFsbCB0aGUgYmFsbG9vbnMuIFlvdSBhcmUgdG8gZmluZCB0aGUgZmluYWwgcmFkaXVzIGZvciBlYWNoIGJhbGxvb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyMDAgMDAwKSAmbWRhc2g7IHRoZSBudW1iZXIgb2YgYmFsbG9vbnMuIFRoZSBuZXh0IG4gbGluZXMgZGVzY3JpYmUgdGhlIGJhbGxvb25zLiBUaGUgaS10aCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4gYW5kIHI8c3ViPmk8XC9zdWI+ICgwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDEgJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGJhbGxvb25zIGFyZSBnaXZlbiBpbiBhIHN0cmljdGx5IGluY3JlYXNpbmcgb3JkZXIgb2YgdGhlIHggY29vcmRpbmF0ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBleGFjdGx5IG4gbGluZXMsIHdpdGggdGhlIGktdGggbGluZSBjb250YWluaW5nIGV4YWN0bHkgb25lIG51bWJlciAmbWRhc2g7IHRoZSByYWRpdXMgb2YgdGhlIGktdGggYmFsbG9vbiBhZnRlciBpbmZsYXRpbmcuIFlvdXIgYW5zd2VyIHdpbGwgYmUgYWNjZXB0ZWQgaWYgaXQgZGlmZmVycyBmcm9tIHRoZSBjb3JyZWN0IG9uZSBieSBubyBtb3JlIHRoYW4gMC4wMDEgZm9yIGVhY2ggbnVtYmVyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: pty115