eolymp
bolt
Try our new interface for solving problems
Problems

Huzita Axiom 6

Huzita Axiom 6

The first formal axiom list for origami was published by Humiaki Huzita and Benedetto Scimemi and has come to be known as the Huzita axioms. These axioms describe the ways in which a fold line can be generated by the alignment of points and lines. A version of the six axioms follows. \begin{enumerate} \item For points \textbf{p_1} and \textbf{p_2}, there is a unique fold that passes through both of them. \item For points \textbf{p_1} and \textbf{p_2}, there is a unique fold that places \textbf{p_1} onto \textbf{p_2}. \item For lines \textbf{l_1} and \textbf{l_2}, there is a fold that places \textbf{l_1} onto \textbf{l_2}. \item For a point \textbf{p_1} and a line \textbf{l_1}, there is a unique fold perpendicular to \textbf{l_1} that passes through point \textbf{p_1}. \item For points \textbf{p_1} and \textbf{p_2} and a line \textbf{l_1}, there is a fold that places \textbf{p_1} onto \textbf{l_1} and passes through \textbf{p_2}. \item For points \textbf{p_1} and \textbf{p_2} and lines \textbf{l_1} and \textbf{l_2}, there is a fold that places \textbf{p_1} onto \textbf{l_1} and \textbf{p_2} onto \textbf{l_2}. \end{enumerate} Roman is a good coder, but he is new to origami construction, so he decided to write a program to calculate the necessary folds for him. He already finished coding the cases for the first five axioms, but now he is stuck on the harder case, the axiom number \textbf{6}. So he decided to hire a team of good coders --- your team --- to implement this case for his program. \InputFile The input consists of one or more test cases. The total number of test cases \textbf{t} is specified in the first line of the input file. It does not exceed \textbf{20000}. Each test case consists of exactly four lines, describing \textbf{l_1}, \textbf{p_1}, \textbf{l_2} and \textbf{p_2}, in that order. Each line is described by four integers --- the coordinates of two different points lying on it: \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2}. Each point is described just by two integers --- its \textbf{x} and \textbf{y} coordinates. All coordinates do not exceed \textbf{10} by their absolute values. It is guaranteed that neither \textbf{p_1} lies on \textbf{l_1} nor \textbf{p_2} lies on \textbf{l_2}. Lines \textbf{l_1} and \textbf{l_2} are different, but points \textbf{p_1} and \textbf{p_2} may be the same. \OutputFile \includegraphics{https://static.e-olymp.com/content/36/361e45f9ff9c6d4b6559a099a8fab8ff79ae2a7e.jpg} For each test case write a separate line with the description of the straight line one should use for folding. Use the same format as in the input --- specify the coordinates of two points on it. Either x or y coordinates of those two points must differ by at least \textbf{10^\{−4\}}. Coordinates must not exceed \textbf{10^9} by their absolute value. The judging program will check that both the distance between \textbf{p_1} after folding and \textbf{l_1}; and the distance between \textbf{p_2} after folding and \textbf{l_2} do not exceed \textbf{10^\{−4\}}. If there are multiple solutions, any one will do. If there are no solutions, output the line of four zeros, separated by spaces. The picture to the right illustrates the first sample. The fold line is dashed.
Time limit 1 second
Memory limit 64 MiB