Garden#5548
There are precious trees in the garden (for simplicity's sake, we will treat them as points on a standard Euclidean plane). Build a square fence around the trees such that:
all the trees are inside the square,
there is at least one tree on every side of the square (a point in the corner counts for both sides).
This way, no one can accuse you of claiming too much land. You do not care for the area of the garden, or the amount of fence needed - any such square will do. Only the trees are important, after all!
The first line contains the number of test cases. The test cases follow.
First line of a test case contains the number of trees (4 \leq n \leq 100\,000). Then lines follow - for j = 1, 2, \ldots, n, -th of these lines contains two integer numbers x_j, y_j - coordinates of the -th tree. The coordinates' absolute values do not exceed 10^9. No two trees coincide.
For each test case, your program should output four lines, each containing a pair of real numbers - the coordinates of the vertices of the square found by your program. Print the values with digits after the decimal point.
Example 1