시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 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+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzljOFx1YjdjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzc0IFx1ZDA2Y1x1YWM4YyBcdWMzMTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzQgXHViNTRjLCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjNTQ4XHVjODE1XHVkNTVjIFx1YzMxM1x1YWUzMFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzMxM1x1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjOWM4XHViN2M5XHVjNzc0IFx1YzU0NFx1Yjc5OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWJkODBcdWQxMzAgXHVjNzA0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5YzhcdWI3YzlcdWM3NDAgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0OFx1YzgxNVx1ZDU1OFx1YWM4YyBcdWMzMTNcdWIyOTQgXHViYzI5XHViYzk1IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc3NCBcdWQwNzQgXHViNTRjXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggeFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQmbmJzcDswLjAwMDAwMVx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJMT0tPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPk4gcmVjdGFuZ2xlcyB3aXRoIGdpdmVuIG1hc3NlcyAobTxzdWI+aTxcL3N1Yj4pIGFuZCBlcXVhbCBsZW5ndGhzICgyKSBhbmQgaGVpZ2h0cyAoaCkgYXJlIGFycmFuZ2VkIGluIGEgQ2FydGVzaWFuIHBsYW5lIHN1Y2ggdGhhdDo8XC9wPlxyXG5cclxuPHA+cmVjdGFuZ2xlIGVkZ2VzIGFyZSBwYXJhbGxlbCB0byB0aGUgY29vcmRpbmF0ZSBheGVzOzxiciBcLz5cclxudGhlIHktY29vcmRpbmF0ZXMgb2YgbG93ZXIgaG9yaXpvbnRhbCBlZGdlcyBhcmUgZGlzdGluY3QgYW5kIGFzc3VtZSB0aGUgZm9sbG93aW5nIHZhbHVlczogMCwgaCwgMmgsIDNoLCAmaGVsbGlwOywgKE4gLSAxKWg7PGJyIFwvPlxyXG50aGUgbG93ZXN0IHJlY3RhbmdsZVx1MjAxZnMgbG93ZXIgbGVmdCBjb3JuZXIgaGFzIGNvb3JkaW5hdGVzICgtMiwgMCksIHdoaWxlIHRoZSBsb3dlciByaWdodCBjb3JuZXIgY29pbmNpZGVzIHdpdGggdGhlIG9yaWdpbjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jvb2sucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA0cHg7IHdpZHRoOjU1M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBYLWNlbnRyZSBvZiBhIHJlY3RhbmdsZSBpcyB0aGUgeC1jb29yZGluYXRlIG9mIHRoZSBtaWRwb2ludCBvZiBpdHMgbG93ZXIgZWRnZS48XC9wPlxyXG5cclxuPHA+VGhlIFgtYmFyeWNlbnRyZSBvZiBvbmUgb3IgbW9yZSByZWN0YW5nbGVzIGlzIHRoZSB3ZWlnaHRlZCBhdmVyYWdlIG9mIHRoZWlyIFgtY2VudHJlcy4gSXQgaXMgY29tcHV0ZWQgYXM8XC9wPlxyXG5cclxuPHA+XFxbWGJhcnljZW50cmU9XFxmcmFje1xcc3VtX3tpfXttX3tpfSBcXGNkb3QgWGNlbnRyZShpKX0gfXtcXHN1bV97aX17bV97aX19fVxcXTxcL3A+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgdGhlIG1hc3Mgb2YgZWFjaCByZWN0YW5nbGUgaXMgbXVsdGlwbGllZCBieSBpdHMgWC1jZW50cmUgYW5kIHRoZSBzdW0gb2YgdGhlc2UgcHJvZHVjdHMgaXMgdGhlbiBkaXZpZGVkIGJ5IHRoZSB0b3RhbCBtYXNzIG9mIHRoZSByZWN0YW5nbGVzLjxcL3A+XHJcblxyXG48cD5BbiBhcnJhbmdlbWVudCBpcyBzdGFibGUgaWYsIGZvciBlYWNoIHJlY3RhbmdsZSBBOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBYLWJhcnljZW50cmUgb2YgcmVjdGFuZ2xlcyBhYm92ZSBBIGhhcyBkaXN0YW5jZSBvZiBhdCBtb3N0IDEgZnJvbSB0aGUgWC1jZW50cmUgb2YgQSAoaS5lLiBpcyBjb250YWluZWQgaW4gdGhlIHgtaW50ZXJ2YWwgdGhhdCBjb3ZlcnMgQSkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW50dWl0aXZlbHksIHN0YWJpbGl0eSBvZiBhbiBhcnJhbmdlbWVudCBjYW4gYmUgdW5kZXJzdG9vZCBhcyB0aGUgcHJlY29uZGl0aW9uIGZvciB0aGUgYXJyYW5nZW1lbnQgdG8gbm90IGZhbGwgYXBhcnQuIFRoZSBhcnJhbmdlbWVudCBpbiB0aGUgZmlndXJlIG9uIHRoZSBsZWZ0IGlzIHVuc3RhYmxlIHNpbmNlIHRoZSBYLWJhcnljZW50cmUgb2YgdGhlIHRvcCB0d28gcmVjdGFuZ2xlcyBmYWxscyBvdXRzaWRlIHRoZSByZWN0YW5nbGUgdW5kZXJuZWF0aCAodGhlIGRpc3RhbmNlIG9mIHRoZSBYLWJhcnljZW50cmUgdG8gdGhlIFgtY2VudHJlIG9mIHRoZSB1bmRlcmx5aW5nIHJlY3RhbmdsZSBpcyBncmVhdGVyIHRoYW4gMSkuIFRoZSBhcnJhbmdlbWVudCBpbiB0aGUgZmlndXJlIG9uIHRoZSByaWdodCBpcyBzdGFibGUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBtYXNzZXMgb2YgYWxsIHJlY3RhbmdsZXMsIGZpbmQgdGhlIGxhcmdlc3QgKCZsZHF1bztyaWdodG1vc3QmcmRxdW87KSBwb3NzaWJsZSB4LWNvb3JkaW5hdGUgb2YgYW55IHJlY3RhbmdsZSBjb3JuZXIgaW4gYSBzdGFibGUgYXJyYW5nZW1lbnQuIFlvdSBhcmUgbm90IGFsbG93ZWQgdG8gY2hhbmdlIHRoZSBvcmRlciBvZiByZWN0YW5nbGVzICh0aGV5IGFyZSBnaXZlbiBmcm9tIHRoZSBsb3dlc3QgdG8gdGhlIGhpZ2hlc3Qgb25lKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbGVzcyB0aGFuIDEwIDAwMCwgdGhlIG1hc3Mgb2YgYSByZWN0YW5nbGUuIFRoZSBtYXNzZXMgYXJlIGdpdmVuIGluIG9yZGVyIGZyb20gdGhlIGxvd2VzdCB0byB0aGUgaGlnaGVzdCByZWN0YW5nbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgcmlnaHRtb3N0IHgtY29vcmRpbmF0ZS4gVGhlIGdpdmVuIHJlc3VsdCBtdXN0IGJlIHdpdGhpbiAwLjAwMDAwMSBvZiB0aGUgb2ZmaWNpYWwgc29sdXRpb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d