410458: GYM104023 C Grass

Charles the Rabbit likes eating grass. As the saying goes, rabbits do not eat the grass by their burrows. Therefore, Charles has to go outside his burrow every day to look for grass to eat.

One day, Charles comes to a two-dimensional plane with many distinct points. He can choose a point $$$A$$$ and another four points $$$B, C, D, E$$$ to connect with $$$A$$$ to form four segments. We consider these four segments as a clump of grass if they meet the following condition:

• Any two of the four segments have only a single point of intersection $$$A$$$ between them.

For example, in the picture below, $$$(1)$$$ is a clump of grass, but $$$(2)$$$ is not one as the intersection of segments $$$AC$$$ and $$$AE$$$ is not only a single point $$$A$$$.

Given $$$n$$$ points on a plane, Charles wants to know whether there exists a clump of grass. If so, help him find a certain one.

The first line contains an integer $$$T$$$ ($$$1 \le T \le 120$$$), indicating the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 25000$$$), indicating the number of points.

Each of the following $$$n$$$ lines contains two integers $$$x,y$$$ ($$$-10^7 \le x,y \le 10^7$$$), indicating that the coordinates of the point are $$$(x,y)$$$. It is guaranteed that all points are distinct.

It is guaranteed that $$$\sum n \le 10^5$$$ over all test cases.

For each test case, if there does not exist a clump of grass, output NO in a single line.

Otherwise, output YES in the first line. Then output two integers separated by a space in the second line, indicating the coordinates of point $$$A$$$. Then output two integers separated by a space in each of the third to sixth lines, indicating the coordinates of the other four points $$$B, C, D, E$$$.

If there is more than one clump of grass, output any.

3
5
0 0
1 1
1 -1
-1 1
-1 -1
3
1 1
4 5
1 4
5
1 0
2 0
3 0
4 0
5 0

YES
0 0
1 1
1 -1
-1 1
-1 -1
NO
NO