Background

This problem may be slightly precision-sensitive. It is recommended to use $\tt long\ double$.

On the night of the Lantern Festival, under the sky.

A group of people looked at a tree, a tree floating in the sky, hoping it would become a cycle.

This tree has $4$ nodes.

“It became a cycle!” someone shouted.
I immediately looked up into the sky…

What a standard square! No matter which astronomer comes to measure it, its angles are standard $90^{\circ}$, and its sides are a perfect $1:1:1:1$…

We saw that tree—no, that elegant and perfect cycle—slowly flying by, fitting exactly into the center of the bright full moon…

Problem Description

You are given the coordinates of $4$ points on the 2D Cartesian coordinate system.

You need to use % magic magic to construct a square such that these $4$ points lie on the lines containing the four sides of the square, respectively.

Input Format

This problem uses multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, there are $4$ lines. Each line contains two integers $x_i, y_i$, representing the coordinates of a point.

Output Format

For each test case, output $4$ lines. Each line contains two real numbers, representing the coordinates of a vertex of the square. You must ensure that the $i$-th given point lies on the side formed by the $i$-th and the $i\ \text{mod}\ 4+1$-th output vertices, and that the side containing the $i$-th given point and the side containing the $i\ \text{mod}\ 4+1$-th given point are adjacent sides.

1
235 423
544 345
563 645
453 435

380.43769007 531.90429895
395.56394564 543.23089701
406.89054360 528.10464158
391.76428803 516.77804352

Hint

This problem uses $\tt SPJ$.

If the answer is not unique, output any one.

It will be accepted ($\tt \green {AC}$) as long as the difference between the lengths of the four sides is $\le 10^{-2}$, the angle between any two adjacent sides is within $\frac{\pi}{2}\pm 10^{-2}$, and letting the given point be $(p,q)$, there exists a point $(p,q+k)\ (|k|\leq 1)$ on the line of the corresponding side.

Constraints:

For $30\%$ of the testdata, $T=1$, $|x_i|, |y_i| \le 10^3$.

For $70\%$ of the testdata, $1 \le T \le 5\times 10^4$, $|x_i|, |y_i| \le 10^6$.

For $100\%$ of the testdata, $1 \le T \le 5\times 10^5$, $|x_i|, |y_i| \le 10^9$.

The testdata guarantees that among the $6$ lines formed by connecting any two points, no two lines are perpendicular to each other, and there is no line parallel to the coordinate axes. No three points are collinear. It is guaranteed that no solution has a side parallel to an axis. It is guaranteed that a solution exists.

For output precision, you need to keep at least $8$ digits after the decimal point.

Translated by ChatGPT 5