시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 29 16 94.118%

문제

드럼통을 직사각형 쓰레기통에 예쁘게 쌓아보려고 한다. 아랫줄을 제외한 모든 실린더는 항상 자기 바로 아랫줄의 실린더 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+PFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJlNFx1YjliMFx1YjM1NFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMTJcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YjU0YywgZG91YmxlXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoVCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzExYyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhYzAxIFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWM5MTFcdWMyZWMgeFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC4gKFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc1OCBcdWJjMTRcdWIyZTVcdWFjZmMgXHVjODExXHVkNTU4XHViYmMwXHViODVjIHlcdWM4OGNcdWQ0NWNcdWIyOTQgXHVkNTZkXHVjMGMxIDFcdWM3NzRcdWIyZTQpLiBOXHVjNzQwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NTggXHVjOTExXHVjMmVjXHVhYzcwXHViOWFjXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCAyLjBcdWM3NzRcdWFjZTAsIFx1YjljZVx1YzU0NFx1YzU3YyAzLjRcdWM3NzRcdWIyZTQuICgyLjBcdWM3NzggXHVjNzc0XHVjNzIwXHViMjk0IFx1YjRkY1x1YjdmY1x1ZDFiNVx1Yzc3NCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgMy40XHVjNzc4IFx1Yzc3NFx1YzcyMFx1YjI5NCBrXHVjOTA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWFjZmMgay0yXHVjOTA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0ZGNcdWI3ZmNcdWQxYjVcdWM3NzQgXHVjMTFjXHViODVjIFx1YzgxMVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjOGMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViN2ZjXHVkMWI1XHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIHhcdWM4OGNcdWQ0NWNcdWM2NDAgeVx1Yzg4Y1x1ZDQ1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjMThjXHVjMjE4XHVjODEwIDRcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdGFja2luZyBDeWxpbmRlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkN5bGluZGVycyAoZS5nLiBvaWwgZHJ1bXMpIChvZiByYWRpdXMgMSBmb290KSBhcmUgc3RhY2tlZCBpbiBhIHJlY3Rhbmd1bGFyIGJpbi4gRWFjaCBjeWxpbmRlciBvbiBhbiB1cHBlciByb3cgcmVzdHMgb24gdHdvIGN5bGluZGVycyBpbiB0aGUgcm93IGJlbG93LiBUaGUgY3lsaW5kZXJzIGluIHRoZSBib3R0b20gcm93IHJlc3Qgb24gdGhlIGZsb29yIGFuZCBkbyBub3Qgcm9sbCBmcm9tIHRoZWlyIG9yaWdpbmFsIHBvc2l0aW9ucy4gRWFjaCByb3cgaGFzIG9uZSBsZXNzIGN5bGluZGVyIHRoYW4gdGhlIHJvdyBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TY3JlZW4lMjBTaG90JTIwMjAxMi0xMC0xMSUyMGF0JTIwJUVDJTk4JUE0JUVEJTlCJTg0JTIwMTBfMjJfNTYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjU3cHg7IHdpZHRoOjQwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoaXMgcHJvYmxlbSBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbG9jYXRpb24gb2YgdGhlIGNlbnRlciBvZiB0aGUgdG9wIGN5bGluZGVyIGZyb20gdGhlIGNlbnRlcnMgb2YgdGhlIGN5bGluZGVycyBvbiB0aGUgYm90dG9tIHJvdy4gQ29tcHV0YXRpb25zIG9mIGludGVybWVkaWF0ZSB2YWx1ZXMgc2hvdWxkIHVzZSBkb3VibGUgcHJlY2lzaW9uLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRoZSBjb3VudCBvZiBwcm9ibGVtIGluc3RhbmNlcywgblByb2IsIGFzIGEgZGVjaW1hbCBpbnRlZ2VyLCAoMSAmbHQ7PSBuUHJvYiAmbHQ7PSAxMDAwKS4gVGhpcyBpcyBmb2xsb3dlZCBieSBuUHJvYiBpbnB1dCBsaW5lcy4gQW4gaW5wdXQgbGluZSBjb25zaXN0cyBvZiB0aGUgbnVtYmVyLCBuLCBvZiBjeWxpbmRlcnMgb24gdGhlIGJvdHRvbSByb3cgZm9sbG93ZWQgYnkgbiBmbG9hdGluZyBwb2ludCB2YWx1ZXMgZ2l2aW5nIHRoZSB4IGNvb3JkaW5hdGVzIG9mIHRoZSBjZW50ZXJzIG9mIHRoZSBjeWxpbmRlcnMgKHRoZSB5IGNvb3JkaW5hdGVzIGFyZSBhbGwgMS4wIHNpbmNlIHRoZSBjeWxpbmRlcnMgYXJlIHJlc3Rpbmcgb24gdGhlIGZsb29yICh5ID0gMC4wKSkuIFRoZSB2YWx1ZSBvZiBuIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMCAoaW5jbHVzaXZlKS4gVGhlIGRpc3RhbmNlIGJldHdlZW4gYWRqYWNlbnQgY2VudGVycyB3aWxsIGJlIGF0IGxlYXN0IDIuMCAoc28gdGhlIGN5bGluZGVycyBkbyBub3Qgb3ZlcmxhcCkgYW5kIGF0IG1vc3QgMy40IChzbyBjeWxpbmRlcnMgYXQgbGV2ZWwgayBjYW5ub3QgdG91Y2ggY3lsaW5kZXJzIGF0IGxldmVsIGsgJm5kYXNoOyAyLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZm9yIGVhY2ggZGF0YSBzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHByb2JsZW0gbnVtYmVyICgxLi4ublByb2IpLCBhIGNvbG9uLCBhIHNwYWNlLCB0aGUgeCBjb29yZGluYXRlIG9mIHRoZSB0b3Btb3N0IGN5bGluZGVyIHRvIDQgZGVjaW1hbCBwbGFjZXMsIGEgc3BhY2UgYW5kIHRoZSB5IGNvb3JkaW5hdGUgb2YgdGhlIHRvcG1vc3QgY3lsaW5kZXIgdG8gNCBkZWNpbWFsIHBsYWNlcy4gTm90ZTogVG8gaGVscCB5b3UgY2hlY2sgeW91ciB3b3JrLCB0aGUgeC1jb29yZGluYXRlIG9mIHRoZSBjZW50ZXIgb2YgdGhlIHRvcCBjeWxpbmRlciBzaG91bGQgYmUgdGhlIGF2ZXJhZ2Ugb2YgdGhlIHgtY29vcmRpbmF0ZXMgb2YgdGhlIGxlZnRtb3N0IGFuZCByaWdodG1vc3QgYm90dG9tIGN5bGluZGVycy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=