시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB65483375.000%

문제

드럼통을 직사각형 쓰레기통에 예쁘게 쌓아보려고 한다. 아랫줄을 제외한 모든 실린더는 항상 자기 바로 아랫줄의 실린더 2개와 닿아있다. 가장 밑 줄의 실린더는 쓰레기통 벽에 닿아있기 때문에, 더이상 굴러가지 않는다. 마지막줄을 제외한 모든 줄은 자기 아랫줄의 드럼통 개수보다 하나 적은 드럼통이 있다.

드럼통의 반지름은 항상 1이다.

가장 위에 있는 실린더의 중심 좌표를 구하는 프로그램을 작성하시오. 값을 계산할 때, double을 사용하면 된다.

입력

첫째 줄에 테스트 케이스의 개수 T(T<=1,000)가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있다. 첫 번째 숫자는 드럼통의 개수 N이 주어진다. 이어서 들어오는 N개의 숫자는 각 드럼통의 중심 x좌표이다. (드럼통의 바닥과 접하므로 y좌표는 항상 1이다). N은 1보다 크거나 같고, 10보다 작거나 같다. 

인접한 두 드럼통의 중심거리는 적어도 2.0이고, 많아야 3.4이다. (2.0인 이유는 드럼통이 겹치지 않기 위해서, 3.4인 이유는 k줄에 있는 드럼통과 k-2줄에 있는 드럼통이 서로 접하지 않게 하기 위해서)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 가장 위에 있는 드럼통의 중심좌표를 공백으로 구분하여 x좌표와 y좌표 순서대로 소수점 4자리까지 출력한다. 

예제 입력 1

5
4 1.0 4.4 7.8 11.2
1 1.0
6 1.0 3.0 5.0 7.0 9.0 11.0
10 1.0 3.0 5.0 7.0 9.0 11.0 13.0 15.0 17.0 20.4
5 1.0 4.4 7.8 11.2 14.6

예제 출력 1

6.1000 4.1607
1.0000 1.0000
6.0000 9.6603
10.7000 15.9100
7.8000 5.2143
W3sicHJvYmxlbV9pZCI6IjI3MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0ZGNcdWI3ZmNcdWQxYjUgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NDQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzRmMFx1YjgwOFx1YWUzMFx1ZDFiNVx1YzVkMCBcdWM2MDhcdWMwNThcdWFjOGMgXHVjMzEzXHVjNTQ0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViN2FiXHVjOTA0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjMmU0XHViOWIwXHViMzU0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3OTBcdWFlMzAgXHViYzE0XHViODVjIFx1YzU0NFx1YjdhYlx1YzkwNFx1Yzc1OCBcdWMyZTRcdWI5YjBcdWIzNTQgMlx1YWMxY1x1YzY0MCBcdWIyZmZcdWM1NDRcdWM3ODhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWJjMTEgXHVjOTA0XHVjNzU4IFx1YzJlNFx1YjliMFx1YjM1NFx1YjI5NCBcdWM0ZjBcdWI4MDhcdWFlMzBcdWQxYjUgXHViY2JkXHVjNWQwIFx1YjJmZlx1YzU0NFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWFkNzRcdWI3ZWNcdWFjMDBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM5MDRcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NDAgXHVjNzkwXHVhZTMwIFx1YzU0NFx1YjdhYlx1YzkwNFx1Yzc1OCBcdWI0ZGNcdWI3ZmNcdWQxYjUgXHVhYzFjXHVjMjE4XHViY2Y0XHViMmU0IFx1ZDU1OFx1YjA5OCBcdWM4MDFcdWM3NDAgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNGRjXHViN2ZjXHVkMWI1XHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TY3JlZW4lMjBTaG90JTIwMjAxMi0xMC0xMSUyMGF0JTIwJUVDJTk4JUE0JUVEJTlCJTg0JTIwMTBfMjJfNTYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjU3cHg7IHdpZHRoOjQwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJlNFx1YjliMFx1YjM1NFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMTJcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YjU0YywgZG91YmxlXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoVCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViMjk0IFx1YWMwMSBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHVjOTExXHVjMmVjIHhcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuIChcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YzgxMVx1ZDU1OFx1YmJjMFx1Yjg1YyB5XHVjODhjXHVkNDVjXHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHVjNzc0XHViMmU0KS4gTlx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzU4IFx1YzkxMVx1YzJlY1x1YWM3MFx1YjlhY1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMi4wXHVjNzc0XHVhY2UwLCBcdWI5Y2VcdWM1NDRcdWM1N2MgMy40XHVjNzc0XHViMmU0LiAoMi4wXHVjNzc4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NzQgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIDMuNFx1Yzc3OCBcdWM3NzRcdWM3MjBcdWIyOTQga1x1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViN2ZjXHVkMWI1XHVhY2ZjIGstMlx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM4MTFcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzE4Y1x1YzIxOFx1YzgxMCA0XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RhY2tpbmcgQ3lsaW5kZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5DeWxpbmRlcnMgKGUuZy4gb2lsIGRydW1zKSAob2YgcmFkaXVzIDEgZm9vdCkgYXJlIHN0YWNrZWQgaW4gYSByZWN0YW5ndWxhciBiaW4uIEVhY2ggY3lsaW5kZXIgb24gYW4gdXBwZXIgcm93IHJlc3RzIG9uIHR3byBjeWxpbmRlcnMgaW4gdGhlIHJvdyBiZWxvdy4gVGhlIGN5bGluZGVycyBpbiB0aGUgYm90dG9tIHJvdyByZXN0IG9uIHRoZSBmbG9vciBhbmQgZG8gbm90IHJvbGwgZnJvbSB0aGVpciBvcmlnaW5hbCBwb3NpdGlvbnMuIEVhY2ggcm93IGhhcyBvbmUgbGVzcyBjeWxpbmRlciB0aGFuIHRoZSByb3cgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMTElMjBhdCUyMCVFQyU5OCVBNCVFRCU5QiU4NCUyMDEwXzIyXzU2LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1N3B4OyB3aWR0aDo0MDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIHByb2JsZW0gaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIGxvY2F0aW9uIG9mIHRoZSBjZW50ZXIgb2YgdGhlIHRvcCBjeWxpbmRlciBmcm9tIHRoZSBjZW50ZXJzIG9mIHRoZSBjeWxpbmRlcnMgb24gdGhlIGJvdHRvbSByb3cuIENvbXB1dGF0aW9ucyBvZiBpbnRlcm1lZGlhdGUgdmFsdWVzIHNob3VsZCB1c2UgZG91YmxlIHByZWNpc2lvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgY291bnQgb2YgcHJvYmxlbSBpbnN0YW5jZXMsIG5Qcm9iLCBhcyBhIGRlY2ltYWwgaW50ZWdlciwgKDEgJmx0Oz0gblByb2IgJmx0Oz0gMTAwMCkuIFRoaXMgaXMgZm9sbG93ZWQgYnkgblByb2IgaW5wdXQgbGluZXMuIEFuIGlucHV0IGxpbmUgY29uc2lzdHMgb2YgdGhlIG51bWJlciwgbiwgb2YgY3lsaW5kZXJzIG9uIHRoZSBib3R0b20gcm93IGZvbGxvd2VkIGJ5IG4gZmxvYXRpbmcgcG9pbnQgdmFsdWVzIGdpdmluZyB0aGUgeCBjb29yZGluYXRlcyBvZiB0aGUgY2VudGVycyBvZiB0aGUgY3lsaW5kZXJzICh0aGUgeSBjb29yZGluYXRlcyBhcmUgYWxsIDEuMCBzaW5jZSB0aGUgY3lsaW5kZXJzIGFyZSByZXN0aW5nIG9uIHRoZSBmbG9vciAoeSA9IDAuMCkpLiBUaGUgdmFsdWUgb2YgbiB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTAgKGluY2x1c2l2ZSkuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIGFkamFjZW50IGNlbnRlcnMgd2lsbCBiZSBhdCBsZWFzdCAyLjAgKHNvIHRoZSBjeWxpbmRlcnMgZG8gbm90IG92ZXJsYXApIGFuZCBhdCBtb3N0IDMuNCAoc28gY3lsaW5kZXJzIGF0IGxldmVsIGsgY2Fubm90IHRvdWNoIGN5bGluZGVycyBhdCBsZXZlbCBrICZuZGFzaDsgMi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBlYWNoIGRhdGEgc2V0IGlzIGEgbGluZSBjb250YWluaW5nIHRoZSBwcm9ibGVtIG51bWJlciAoMS4uLm5Qcm9iKSwgYSBjb2xvbiwgYSBzcGFjZSwgdGhlIHggY29vcmRpbmF0ZSBvZiB0aGUgdG9wbW9zdCBjeWxpbmRlciB0byA0IGRlY2ltYWwgcGxhY2VzLCBhIHNwYWNlIGFuZCB0aGUgeSBjb29yZGluYXRlIG9mIHRoZSB0b3Btb3N0IGN5bGluZGVyIHRvIDQgZGVjaW1hbCBwbGFjZXMuIE5vdGU6IFRvIGhlbHAgeW91IGNoZWNrIHlvdXIgd29yaywgdGhlIHgtY29vcmRpbmF0ZSBvZiB0aGUgY2VudGVyIG9mIHRoZSB0b3AgY3lsaW5kZXIgc2hvdWxkIGJlIHRoZSBhdmVyYWdlIG9mIHRoZSB4LWNvb3JkaW5hdGVzIG9mIHRoZSBsZWZ0bW9zdCBhbmQgcmlnaHRtb3N0IGJvdHRvbSBjeWxpbmRlcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==