Chaos Begin

Long long ago, there were $n$ points $a_1,a_2,\dots,a_n$ on the 2D plane. The world keeps stable for a long time. However, it begins to be chaotic recently when another $n$ points $b_1,b_2,\dots,b_n$ appeared, where $b_i=a_i+(\Delta x,\Delta y)$. And now, these $2n$ points have already lost their identifiers.

You are given these $2n$ points in an arbitrary order, you need to figure out all the possible $(\Delta x,\Delta y)$ to help the world recover from chaos.

The first line contains a single integer $T$ ($1 \leq T \leq 100$), the number of test cases. For each test case:

The first line of the input contains a single integer $n$ ($1 \leq n \leq 50\,000$), denoting the number of initial points.

In the next $2n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($|x_i|,|y_i|\leq 10^8$), describing the coordinate of a current point.

It is guaranteed that the x-coordinate and y-coordinate of each initial point are chosen uniformly at random from integers in $[-v,v]$, where $v$ is chosen in $[10^7,10^8]$. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.

It is also guaranteed that the sum of all $n$ is at most $300\,000$.

For each test case, first output a single line containing an integer $k$, denoting the number of possible $(\Delta x,\Delta y)$. Then output $k$ lines, each line contains two integers $\Delta x$ and $\Delta y$. It is guaranteed that $k\geq 1$, and when $k\geq 2$, you should print the answers in ascending order of $\Delta x$, and then in ascending order of $\Delta y$ in case of a tie.

1
3
1 2
3 4
8 9
7 8
6 7
2 3

2
-5 -5
5 5

2023“钉耙编程”中国大学生算法设计超级联赛（3）