Stacking Drums

Drums of radius 1 are stacked inside a rectangular trash bin. The drums in the bottom row are held in place by the floor and walls, so they do not roll. Every drum above the bottom row touches two adjacent drums directly below it. Except for the top row, if a row contains k drums, the row immediately above it contains k-1 drums.

Given the x-coordinates of the centers of the drums in the bottom row, find the center coordinates of the drum at the very top after stacking all drums by this rule. Double precision floating point arithmetic is sufficient for all calculations.

The first line contains the number of test cases T. T is at most 1000. Each test case is given on one line. The first value is N, the number of drums in the bottom row, followed by N numbers giving the x-coordinates of the centers of those drums. Since every bottom-row drum touches the floor, each of their center y-coordinates is 1.

N is between 1 and 10, inclusive. In the bottom row, the distance between the centers of two adjacent drums is at least 2.0 and at most 3.4. The lower bound 2.0 prevents drums from overlapping, and the upper bound 3.4 prevents unnecessary contact with a drum two rows above.

For each test case, print one line containing the center coordinates of the top drum. Print the x-coordinate followed by the y-coordinate, separated by one space, with both values rounded to 4 digits after the decimal point.