시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29 27 14 93.333%

문제

드럼통을 직사각형 쓰레기통에 예쁘게 쌓아보려고 한다. 아랫줄 을 제외한 모든 실린더는 항상 자기 바로 아랫줄의 실린더 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
W3sicHJvYmxlbV9pZCI6IjI3MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0ZGNcdWI3ZmNcdWQxYjUgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NDQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzRmMFx1YjgwOFx1YWUzMFx1ZDFiNVx1YzVkMCBcdWM2MDhcdWMwNThcdWFjOGMgXHVjMzEzXHVjNTQ0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViN2FiXHVjOTA0IFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzJlNFx1YjliMFx1YjM1NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzkwXHVhZTMwIFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3YWJcdWM5MDRcdWM3NTggXHVjMmU0XHViOWIwXHViMzU0IDJcdWFjMWNcdWM2NDAgXHViMmZmXHVjNTQ0XHVjNzg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHViYzExIFx1YzkwNFx1Yzc1OCBcdWMyZTRcdWI5YjBcdWIzNTRcdWIyOTQgXHVjNGYwXHViODA4XHVhZTMwXHVkMWI1IFx1YmNiZFx1YzVkMCBcdWIyZmZcdWM1NDRcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWIzNTRcdWM3NzRcdWMwYzEgXHVhZDc0XHViN2VjXHVhYzAwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjOTA0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjOTA0XHVjNzQwIFx1Yzc5MFx1YWUzMCBcdWM1NDRcdWI3YWJcdWM5MDRcdWM3NTggXHViNGRjXHViN2ZjXHVkMWI1IFx1YWMxY1x1YzIxOFx1YmNmNFx1YjJlNCBcdWQ1NThcdWIwOTggXHVjODAxXHVjNzQwIFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDAgXHVkNTZkXHVjMGMxIDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMTElMjBhdCUyMCVFQyU5OCVBNCVFRCU5QiU4NCUyMDEwXzIyXzU2LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1N3B4OyB3aWR0aDo0MDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyZTRcdWI5YjBcdWIzNTRcdWM3NTggXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhYzEyXHVjNzQ0IFx1YWM4Y1x1YzBiMFx1ZDU2MCBcdWI1NGMsIGRvdWJsZVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKFQmbHQ7PTEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHViNGU0XHVjNWI0XHVjNjI0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViMjk0IFx1YWMwMSBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHVjOTExXHVjMmVjIHhcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuIChcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YzgxMVx1ZDU1OFx1YmJjMFx1Yjg1YyB5XHVjODhjXHVkNDVjXHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHVjNzc0XHViMmU0KS4gTlx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzU4IFx1YzkxMVx1YzJlY1x1YWM3MFx1YjlhY1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMi4wXHVjNzc0XHVhY2UwLCBcdWI5Y2VcdWM1NDRcdWM1N2MgMy40XHVjNzc0XHViMmU0LiAoMi4wXHVjNzc4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NzQgXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIDMuNFx1Yzc3OCBcdWM3NzRcdWM3MjBcdWIyOTQga1x1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViN2ZjXHVkMWI1XHVhY2ZjIGstMlx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM4MTFcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzE4Y1x1YzIxOFx1YzgxMCA0XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RhY2tpbmcgQ3lsaW5kZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5DeWxpbmRlcnMgKGUuZy4gb2lsIGRydW1zKSAob2YgcmFkaXVzIDEgZm9vdCkgYXJlIHN0YWNrZWQgaW4gYSByZWN0YW5ndWxhciBiaW4uIEVhY2ggY3lsaW5kZXIgb24gYW4gdXBwZXIgcm93IHJlc3RzIG9uIHR3byBjeWxpbmRlcnMgaW4gdGhlIHJvdyBiZWxvdy4gVGhlIGN5bGluZGVycyBpbiB0aGUgYm90dG9tIHJvdyByZXN0IG9uIHRoZSBmbG9vciBhbmQgZG8gbm90IHJvbGwgZnJvbSB0aGVpciBvcmlnaW5hbCBwb3NpdGlvbnMuIEVhY2ggcm93IGhhcyBvbmUgbGVzcyBjeWxpbmRlciB0aGFuIHRoZSByb3cgYmVsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMTElMjBhdCUyMCVFQyU5OCVBNCVFRCU5QiU4NCUyMDEwXzIyXzU2LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1N3B4OyB3aWR0aDo0MDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIHByb2JsZW0gaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIGxvY2F0aW9uIG9mIHRoZSBjZW50ZXIgb2YgdGhlIHRvcCBjeWxpbmRlciBmcm9tIHRoZSBjZW50ZXJzIG9mIHRoZSBjeWxpbmRlcnMgb24gdGhlIGJvdHRvbSByb3cuIENvbXB1dGF0aW9ucyBvZiBpbnRlcm1lZGlhdGUgdmFsdWVzIHNob3VsZCB1c2UgZG91YmxlIHByZWNpc2lvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgY291bnQgb2YgcHJvYmxlbSBpbnN0YW5jZXMsIG5Qcm9iLCBhcyBhIGRlY2ltYWwgaW50ZWdlciwgKDEgJmx0Oz0gblByb2IgJmx0Oz0gMTAwMCkuIFRoaXMgaXMgZm9sbG93ZWQgYnkgblByb2IgaW5wdXQgbGluZXMuIEFuIGlucHV0IGxpbmUgY29uc2lzdHMgb2YgdGhlIG51bWJlciwgbiwgb2YgY3lsaW5kZXJzIG9uIHRoZSBib3R0b20gcm93IGZvbGxvd2VkIGJ5IG4gZmxvYXRpbmcgcG9pbnQgdmFsdWVzIGdpdmluZyB0aGUgeCBjb29yZGluYXRlcyBvZiB0aGUgY2VudGVycyBvZiB0aGUgY3lsaW5kZXJzICh0aGUgeSBjb29yZGluYXRlcyBhcmUgYWxsIDEuMCBzaW5jZSB0aGUgY3lsaW5kZXJzIGFyZSByZXN0aW5nIG9uIHRoZSBmbG9vciAoeSA9IDAuMCkpLiBUaGUgdmFsdWUgb2YgbiB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTAgKGluY2x1c2l2ZSkuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIGFkamFjZW50IGNlbnRlcnMgd2lsbCBiZSBhdCBsZWFzdCAyLjAgKHNvIHRoZSBjeWxpbmRlcnMgZG8gbm90IG92ZXJsYXApIGFuZCBhdCBtb3N0IDMuNCAoc28gY3lsaW5kZXJzIGF0IGxldmVsIGsgY2Fubm90IHRvdWNoIGN5bGluZGVycyBhdCBsZXZlbCBrICZuZGFzaDsgMi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBlYWNoIGRhdGEgc2V0IGlzIGEgbGluZSBjb250YWluaW5nIHRoZSBwcm9ibGVtIG51bWJlciAoMS4uLm5Qcm9iKSwgYSBjb2xvbiwgYSBzcGFjZSwgdGhlIHggY29vcmRpbmF0ZSBvZiB0aGUgdG9wbW9zdCBjeWxpbmRlciB0byA0IGRlY2ltYWwgcGxhY2VzLCBhIHNwYWNlIGFuZCB0aGUgeSBjb29yZGluYXRlIG9mIHRoZSB0b3Btb3N0IGN5bGluZGVyIHRvIDQgZGVjaW1hbCBwbGFjZXMuIE5vdGU6IFRvIGhlbHAgeW91IGNoZWNrIHlvdXIgd29yaywgdGhlIHgtY29vcmRpbmF0ZSBvZiB0aGUgY2VudGVyIG9mIHRoZSB0b3AgY3lsaW5kZXIgc2hvdWxkIGJlIHRoZSBhdmVyYWdlIG9mIHRoZSB4LWNvb3JkaW5hdGVzIG9mIHRoZSBsZWZ0bW9zdCBhbmQgcmlnaHRtb3N0IGJvdHRvbSBjeWxpbmRlcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d