Divide and Conquer

Given $n$ points in 2D plane, where $n \equiv 0 \pmod{4}$, no two points coincide and no three points are collinear. Find two intersecting lines satisfying that no given points lie in the two lines and that for each of the four divided areas, there are exactly $\frac{n}{4}$ given points. If multiple solutions exist, print any one of them. If no solution, print "-1" in one line.

The first line contains one positive integer $T$ ($1\le T \le 20$), denoting the number of test cases. For each test case:

The first line contains one integer $n\,(4 \le n \le 50000)$, denoting the number of given points.

Following $n$ lines each contains two integers $x_i, y_i\,(|x_i|, |y_i| \le 10^6)$, denoting one given point $(x_i, y_i)$.

It is guaranteed that $\sum n \le 10^5, \, n \equiv 0 \pmod{4}$, that no two points coincide and that no three points are collinear.

For each test case:

If no solution, print "-1" in one line. Else print two lines each containing four integers $x_1, y_1, x_2, y_2 \, ((x_1, y_1) \neq (x_2, y_2))$ with absolute value not exceeding $10^9$, denoting one line passing $(x_1, y_1), (x_2, y_2)$ simultaneously.

2
4
-1 -1
-1 1
1 -1
1 1
8
0 0
0 1
2 0
2 1
1 2
1 3
3 2
3 3

0 1 0 -1
1 0 -1 0
1 0 2 3
0 2 3 1

2020 Multi-University Training Contest 10