19271번 - Construct Point 스페셜 저지다국어

You have $Q$ triangles, numbered $1$ through $Q$.

The coordinates of the vertices of the $i$-th triangle are $(x_{1_i}, y_{1_i})$, $(x_{2_i}, y_{2_i})$ and $(x_{3_i}, y_{3_i})$ in counterclockwise order. Here, $x_{1_i}$, $x_{2_i}$, $x_{3_i}$, $y_{1_i}$, $y_{2_i}$ and $y_{3_i}$ are all integers.

For each triangle, determine if there exists a grid point contained in its interior (excluding the boundary). If it exists, construct one such point.

Input is given in the following format:

$Q$

$x_{1_1}$ $y_{1_1}$ $x_{2_1}$ $y_{2_1}$ $x_{3_1}$ $y_{3_1}$

$x_{1_2}$ $y_{1_2}$ $x_{2_2}$ $y_{2_2}$ $x_{3_2}$ $y_{3_2}$

$\ldots$

$x_{1_Q}$ $y_{1_Q}$ $x_{2_Q}$ $y_{2_Q}$ $x_{3_Q}$ $y_{3_Q}$

Output should contain $Q$ lines.

In the $i$-th line, if there is no grid point contained in the interior (excluding the boundary) of Triangle $i$, print "-1 -1". If it exists, choose one such grid point, then print its $x$-coordinate and $y$-coordinate with a space in between.

All input values are integers, $1 \leq Q \leq 10\,000$, $0 \leq x_{1_i}, x_{2_i}, x_{3_i}, y_{1_i}, y_{2_i}, y_{3_i} \leq 10^9$, $(x_{1_i}, y_{1_i})$, $(x_{2_i}, y_{2_i})$ and $(x_{3_i}, y_{3_i})$ are listed in counterclockwise order, the triangles are non-degenerate.