P8309 〈 TREE's OI 2022 Spring 〉Dimension-2 Square

# 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… 

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.

**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.

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.

**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