32470번 - Running in the Plane 스페셜 저지다국어

You are given a set $S=\{(a_1,b_1) ,(a_2,b_2) ,\dots ,(a_n,b_n)\}$ of $n$ points in the plane. All coordinates of $S$ are integers.

A set $T=\{(c_1,d_1) ,(c_2,d_2) ,\dots ,(c_m,d_m)\}$ of $m$ 2-dimensional vectors is called a good set of $S$ if it satisfies the following:

1. There exists a nonempty finite sequence $((x_0,y_0) ,(x_1,y_1) ,\dots ,(x_l,y_l))$ of points in the plane such that
   1. $(x_0,y_0) =(0,0)$.
   2. For all points $p$ in $S$, there exists an integer $i$ ($0\le i\le l$) such that $(x_i,y_i) =p$.
   3. For all integers $i$ ($0\le i<l$), the vector $(x_{i+1}-x_i,y_{i+1}-y_i)$ is in $T$.
2. For all integers $i$ ($1\le i\le m$), two numbers $c_i$ and $d_i$ are integers between $-10^{18}$ and $10^{18}$ inclusive.

Find any good set of minimum size.

The input consists of multiple test cases. The first line contains an integer $Q$ — the number of test cases. The description of the test cases follows. For each test case:

• The first line of the test case contains an integer $n$ — the number of points in $S$.
• The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ — the coordinates of each point in $S$.

For each test case:

• Let $T=\{(c_1,d_1) ,(c_2,d_2) ,\dots ,(c_m,d_m)\}$ be a minimum-size good set of $S$.
• In the first line of the test case, print an integer $m$ — the number of vectors in $T$.
• In the $i$-th of the next $m$ lines, print two integers $c_i$ and $d_i$ — the coordinates of each vector.

If there are multiple solutions, print any of them.

It can be proved that, under the constraints of this problem, a good set of $S$ with size at most $10\times n$ always exists.

• $1\le Q\le 50\, 000$
• The sum of $n$ over all test cases does not exceed $10^5$.
• $2\le n\le 10^5$
• $-10^8\le a_i,b_i\le 10^8$ ($1\le i\le n$)
• $(a_i,b_i)\ne(a_j,b_j)$ ($1\le i<j\le n$)
• $m\ge 0$
• $-10^{18}\le c_i,d_i\le 10^{18}$ ($1\le i\le m$)
• $(c_i,d_i)\ne(c_j,d_j)$ ($1\le i<j\le m$)

In the first test case, $T=\{(-10,10)\}$ is a minimum-size good set of $S=\{(-30,30) ,(-50,50)\}$.

We can take a sequence $((0,0) ,(-10,10) ,(-20,20) ,\underline{(-30,30)} ,(-40,40) ,\underline{(-50,50)})$. Here, the underlined points are in $S$.

In the second test case, $T=\{(1,0) ,(1,1)\}$ is a minimum-size good set of $S=\{(2,1) ,(1,0) ,(4,1)\}$.

We can take a sequence $((0,0) ,\underline{(1,0)} ,\underline{(2,1)} ,(3,1) ,\underline{(4,1)})$.