시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 2 2 100.000%

문제

질량이 mi, 길이가 2, 높이가 h인 직사각형이 N개가 있다. 이 직사각형은 2차원 평면에 다음과 같이 쌓여져 있다.

  • 직사각형의 변은 모두 축에 평행하다.
  • 직사각형 아랫변의 y좌표는 모두 다르고, 다음이 0, h, 2h, 3h, ..., (N-1)h값을 갖는다.
  • 가장 아래에 있는 직사각형의 왼쪽 아래 좌표는 (-2,0)이고, 오른쪽 아래의 좌표는 (0,0)이다.

직사각형의 x중심은 아랫변의 중점이다.

하나 또는 그 이상 직사각형의 무게중심은 직사각형의 x좌표와 무게를 이용해서 아래와 같이 계산할 수 있다.

각 직사각형 A보다 위에 있는 직사각형의 무게중심과 A의 x중심의 거리가 많아야 1이 되도록 직사각형을 쌓는다면, 안정한 쌓기라고 한다.

직사각형을 안정하게 쌓는다면, 직사각형은 무너지지 않을 것이다. 왼쪽 그림은 안정한 배치가 아니다. 그 이유는 가장 위의 두 직사각형의 무게중심과 바로 아래있는 직사각형의 x중심의 거리가 1을 넘기 때문이다. 오른족 그림은 안정한 쌓기이다.

모든 직사각형의 질량이 주어졌을 때, 모든 직사각형의 꼭짓점 중 가장 오른쪽에 있는 꼭짓점이 크게 쌓는 방법을 구하는 프로그램을 작성하시오. 이때, 직사각형은 안정한 쌓기이어야 하고, 입력으로 주어진 순서대로 쌓아야 한다.

입력

첫째 줄에 직사각형의 개수 N이 주어진다. (2 ≤ N ≤ 300,000)

다음 N개 줄에는 직사각형의 질량이 아래 직사각형부터 위 직사각형까지 순서대로 주어진다. 질량은 10,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 안정하게 쌓는 방법 중에서 가장 오른쪽 꼭짓점이 클 때의 오른쪽 꼭짓점의 x좌표를 출력한다. 정답과의 오차는 0.000001까지 허용한다.

예제 입력 1

2
1
1

예제 출력 1

1.000000
W3sicHJvYmxlbV9pZCI6IjI4MDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjNDUgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzhcdWI3YzlcdWM3NzQgbTxzdWI+aTxcL3N1Yj4sIFx1YWUzOFx1Yzc3NFx1YWMwMCAyLCBcdWIxOTJcdWM3NzRcdWFjMDAgaFx1Yzc3OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgTlx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgMlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzRcdWM1ZDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMzMTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NDAgXHViYWE4XHViNDUwIFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM1NDRcdWI3YWJcdWJjYzBcdWM3NTggeVx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHVhY2UwLCBcdWIyZTRcdWM3NGNcdWM3NzQgMCwgaCwgMmgsIDNoLCAuLi4sIChOLTEpaFx1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoLTIsMClcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OThcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0ICgwLDApXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYm9vay5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDRweDsgd2lkdGg6NTUzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IHhcdWM5MTFcdWMyZWNcdWM3NDAgXHVjNTQ0XHViN2FiXHViY2MwXHVjNzU4IFx1YzkxMVx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJiMzRcdWFjOGNcdWM5MTFcdWMyZWNcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWM2NDAgXHViYjM0XHVhYzhjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RhdW1fZXF1YXRpb25fMTM2MzE4NDAyNDUyMC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDNweDsgd2lkdGg6NDcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBBXHViY2Y0XHViMmU0IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmIzNFx1YWM4Y1x1YzkxMVx1YzJlY1x1YWNmYyBBXHVjNzU4IHhcdWM5MTFcdWMyZWNcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIFx1YjljZVx1YzU0NFx1YzU3YyAxXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjMzEzXHViMjk0XHViMmU0XHViYTc0LCBcdWM1NDhcdWM4MTVcdWQ1NWMgXHVjMzEzXHVhZTMwXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YzU0OFx1YzgxNVx1ZDU1OFx1YWM4YyBcdWMzMTNcdWIyOTRcdWIyZTRcdWJhNzQsIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWJiMzRcdWIxMDhcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM1NDhcdWM4MTVcdWQ1NWMgXHViYzMwXHVjZTU4XHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNzU4IFx1YjQ1MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViYjM0XHVhYzhjXHVjOTExXHVjMmVjXHVhY2ZjIFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3OThcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IHhcdWM5MTFcdWMyZWNcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIDFcdWM3NDQgXHViMTE4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVjNjI0XHViOTc4XHVjODcxIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM1NDhcdWM4MTVcdWQ1NWMgXHVjMzEzXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzljOFx1YjdjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0IFx1ZDA2Y1x1YWM4YyBcdWMzMTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMsIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM1NDhcdWM4MTVcdWQ1NWMgXHVjMzEzXHVhZTMwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjMzEzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM5YzhcdWI3YzlcdWM3NzQgXHVjNTQ0XHViNzk4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YmQ4MFx1ZDEzMCBcdWM3MDQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzljOFx1YjdjOVx1Yzc0MCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTQ4XHVjODE1XHVkNTU4XHVhYzhjIFx1YzMxM1x1YjI5NCBcdWJjMjlcdWJjOTUgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0IFx1ZDA3NCBcdWI1NGNcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjI5NCZuYnNwOzAuMDAwMDAxXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQkxPS09WSSIsImRlc2NyaXB0aW9uIjoiPHA+TiByZWN0YW5nbGVzIHdpdGggZ2l2ZW4gbWFzc2VzIChtPHN1Yj5pPFwvc3ViPikgYW5kIGVxdWFsIGxlbmd0aHMgKDIpIGFuZCBoZWlnaHRzIChoKSBhcmUgYXJyYW5nZWQgaW4gYSBDYXJ0ZXNpYW4gcGxhbmUgc3VjaCB0aGF0OjxcL3A+XHJcblxyXG48cD5yZWN0YW5nbGUgZWRnZXMgYXJlIHBhcmFsbGVsIHRvIHRoZSBjb29yZGluYXRlIGF4ZXM7PGJyIFwvPlxyXG50aGUgeS1jb29yZGluYXRlcyBvZiBsb3dlciBob3Jpem9udGFsIGVkZ2VzIGFyZSBkaXN0aW5jdCBhbmQgYXNzdW1lIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiAwLCBoLCAyaCwgM2gsICZoZWxsaXA7LCAoTiAtIDEpaDs8YnIgXC8+XHJcbnRoZSBsb3dlc3QgcmVjdGFuZ2xlXHUyMDFmcyBsb3dlciBsZWZ0IGNvcm5lciBoYXMgY29vcmRpbmF0ZXMgKC0yLCAwKSwgd2hpbGUgdGhlIGxvd2VyIHJpZ2h0IGNvcm5lciBjb2luY2lkZXMgd2l0aCB0aGUgb3JpZ2luPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYm9vay5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDRweDsgd2lkdGg6NTUzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIFgtY2VudHJlIG9mIGEgcmVjdGFuZ2xlIGlzIHRoZSB4LWNvb3JkaW5hdGUgb2YgdGhlIG1pZHBvaW50IG9mIGl0cyBsb3dlciBlZGdlLjxcL3A+XHJcblxyXG48cD5UaGUgWC1iYXJ5Y2VudHJlIG9mIG9uZSBvciBtb3JlIHJlY3RhbmdsZXMgaXMgdGhlIHdlaWdodGVkIGF2ZXJhZ2Ugb2YgdGhlaXIgWC1jZW50cmVzLiBJdCBpcyBjb21wdXRlZCBhczxcL3A+XHJcblxyXG48cD5cXFtYYmFyeWNlbnRyZT1cXGZyYWN7XFxzdW1fe2l9e21fe2l9IFxcY2RvdCBYY2VudHJlKGkpfSB9e1xcc3VtX3tpfXttX3tpfX19XFxdPFwvcD5cclxuXHJcbjxwPkluIG90aGVyIHdvcmRzLCB0aGUgbWFzcyBvZiBlYWNoIHJlY3RhbmdsZSBpcyBtdWx0aXBsaWVkIGJ5IGl0cyBYLWNlbnRyZSBhbmQgdGhlIHN1bSBvZiB0aGVzZSBwcm9kdWN0cyBpcyB0aGVuIGRpdmlkZWQgYnkgdGhlIHRvdGFsIG1hc3Mgb2YgdGhlIHJlY3RhbmdsZXMuPFwvcD5cclxuXHJcbjxwPkFuIGFycmFuZ2VtZW50IGlzIHN0YWJsZSBpZiwgZm9yIGVhY2ggcmVjdGFuZ2xlIEE6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIFgtYmFyeWNlbnRyZSBvZiByZWN0YW5nbGVzIGFib3ZlIEEgaGFzIGRpc3RhbmNlIG9mIGF0IG1vc3QgMSBmcm9tIHRoZSBYLWNlbnRyZSBvZiBBIChpLmUuIGlzIGNvbnRhaW5lZCBpbiB0aGUgeC1pbnRlcnZhbCB0aGF0IGNvdmVycyBBKS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbnR1aXRpdmVseSwgc3RhYmlsaXR5IG9mIGFuIGFycmFuZ2VtZW50IGNhbiBiZSB1bmRlcnN0b29kIGFzIHRoZSBwcmVjb25kaXRpb24gZm9yIHRoZSBhcnJhbmdlbWVudCB0byBub3QgZmFsbCBhcGFydC4gVGhlIGFycmFuZ2VtZW50IGluIHRoZSBmaWd1cmUgb24gdGhlIGxlZnQgaXMgdW5zdGFibGUgc2luY2UgdGhlIFgtYmFyeWNlbnRyZSBvZiB0aGUgdG9wIHR3byByZWN0YW5nbGVzIGZhbGxzIG91dHNpZGUgdGhlIHJlY3RhbmdsZSB1bmRlcm5lYXRoICh0aGUgZGlzdGFuY2Ugb2YgdGhlIFgtYmFyeWNlbnRyZSB0byB0aGUgWC1jZW50cmUgb2YgdGhlIHVuZGVybHlpbmcgcmVjdGFuZ2xlIGlzIGdyZWF0ZXIgdGhhbiAxKS4gVGhlIGFycmFuZ2VtZW50IGluIHRoZSBmaWd1cmUgb24gdGhlIHJpZ2h0IGlzIHN0YWJsZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG1hc3NlcyBvZiBhbGwgcmVjdGFuZ2xlcywgZmluZCB0aGUgbGFyZ2VzdCAoJmxkcXVvO3JpZ2h0bW9zdCZyZHF1bzspIHBvc3NpYmxlIHgtY29vcmRpbmF0ZSBvZiBhbnkgcmVjdGFuZ2xlIGNvcm5lciBpbiBhIHN0YWJsZSBhcnJhbmdlbWVudC4gWW91IGFyZSBub3QgYWxsb3dlZCB0byBjaGFuZ2UgdGhlIG9yZGVyIG9mIHJlY3RhbmdsZXMgKHRoZXkgYXJlIGdpdmVuIGZyb20gdGhlIGxvd2VzdCB0byB0aGUgaGlnaGVzdCBvbmUpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiByZWN0YW5nbGVzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gMTAgMDAwLCB0aGUgbWFzcyBvZiBhIHJlY3RhbmdsZS4gVGhlIG1hc3NlcyBhcmUgZ2l2ZW4gaW4gb3JkZXIgZnJvbSB0aGUgbG93ZXN0IHRvIHRoZSBoaWdoZXN0IHJlY3RhbmdsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCByaWdodG1vc3QgeC1jb29yZGluYXRlLiBUaGUgZ2l2ZW4gcmVzdWx0IG11c3QgYmUgd2l0aGluIDAuMDAwMDAxIG9mIHRoZSBvZmZpY2lhbCBzb2x1dGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=