Problem Description

There are two disjoint squares $A$ and $B$ on the 2D Cartesian coordinate plane. Please find any line that separates them so that the two squares lie on different sides of the line.

Note: This line must not have any common point with either square.

Input Format

The input contains multiple test cases.

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

For each test case, there are $8$ lines. Each line contains $2$ real numbers, describing the $x$ coordinate and $y$ coordinate of a point. The first four lines give the coordinates of the four vertices of square $A$, and the last four lines give the coordinates of the four vertices of square $B$.

It is guaranteed that the four vertices can form a square, but the order can be arbitrary. The two squares are guaranteed to be disjoint.

There is no guarantee that the sides of the squares are parallel to the coordinate axes.

Output Format

For each test case, output one line with three real numbers $a, b, c$, meaning that the line you find has equation $ax + by = c$.

1
1.0 1.0
2.0 2.0
1.0 2.0
2.0 1.0
0.0 0.0
-0.5 -0.5
0.0 -1.0
0.5 -0.5

0.0 1.0 0.5

Hint

$1 \le T \le 10000$.

The absolute value of each input coordinate does not exceed $10^3$, and there are at most $3$ digits after the decimal point.

The SPJ uses double-precision floating point numbers to verify your answer, so please avoid precision errors as much as possible.

Ways to avoid precision errors include: do not output numbers with extremely large or extremely small absolute values, output as many digits after the decimal point as possible, use eps when comparing values, etc.

Hack testdata has been added after the contest.

Translated by ChatGPT 5