33748번 - Hell of Optimizing Geometric Construction 스페셜 저지다국어

문제

One day, dnialh mentioned that optimizing geometric construction perfectly is not possible. Oh, very well. You will see about that.

You are given a positive integer $n$ such that 2ドル \le n \le 1,320円$. Please find a sequence of $n$ points on the plane, $X_1,X_2,\cdots,X_n,ドル satisfying the following constraints.

• The coordinates of each point are integers in the range $[-1,000,1円,000円]$.
• No two points share the same coordinates.
• For each 1ドル \le i \le n,ドル the closest point to $X_i$ other than $X_i$ itself is unique. Let the index of this unique point be $f(i)$.
• Let $p$ be a sequence of $n$ integers defined by $p_1=1$ and $p_{i+1}=f(p_i)$ for 1ドル \le i < n$. Then, $p$ is a permutation of 1,2,ドル\cdots,n$.

It is proven that such a sequence of points exists under the constraints of this task.

입력

A positive integer $n$ is given on one line. (2ドル \le n \le 1,320円$)

출력

Output $n$ lines. The $i$-th line must contain $x_i$ and $y_i,ドル the coordinates of $X_i,ドル separated by a space. ($-1,000円 \le x_i,y_i \le 1,000円$)

제한

노트

In the samples, $n=4$ and $X=[(-2,-2),(1,2),(-2,2),(2,1)]$.

Here, $f(i)$ is determined as follows.

• Other than $X_1,ドル the unique closest point to $X_1$ is $X_3$. Therefore, $f(1)=3$.
• Other than $X_2,ドル the unique closest point to $X_2$ is $X_4$. Therefore, $f(2)=4$.
• Other than $X_3,ドル the unique closest point to $X_3$ is $X_2$. Therefore, $f(3)=2$.
• Other than $X_4,ドル the unique closest point to $X_4$ is $X_2$. Therefore, $f(4)=2$.

Now, one can manually verify that the resultant sequence $p=[1,3,2,4]$ is a permutation of 1,2,3,4ドル$. Therefore, the sequence of points satisfies the constraints.