Background

You can download the input files here.

Problem Description

Azerbaijan is famous for its carpets. As a master carpet designer, you want to draw a polyline in your new design. A polyline is a sequence of line segments in the 2D plane consisting of $t$ segments. These segments are defined by a sequence of $t+1$ points $p_0,\ldots,p_t$ as follows: for every $0\le j\le t- 1$, there is a segment connecting points $p_j$ and $p_{j+1}$.

To complete this new design, you have already marked $n$ small dots in the 2D plane. The coordinates of small dot $i$ ($1 < i < n$) are $(x_i,y_i)$. There are no two small dots with the same $x$ coordinate or the same $y$ coordinate.

Now you want to find a point sequence $(sx_0,sy_0),(sx_1, sy_1)\ldots (sx_k, sy_k)$ such that the polyline defined by this sequence satisfies:

• The polyline starts from $(0,0)$ (i.e., $sx_0=0$ and $sy_0=0$),
• The polyline passes through all small dots (they do not have to be endpoints of segments), and
• The polyline consists only of horizontal and vertical segments (for any two consecutive points defining the polyline, their $x$ coordinates or their $y$ coordinates are equal).

The polyline may self-intersect or overlap in any way. Formally, each point on the plane may belong to any number of segments of the polyline.

This is a partial-scoring output-only problem. You will be given $10$ input files that specify the positions of the small dots. For each input file, you need to submit an output file describing a polyline that satisfies the requirements. For each output file that provides a valid polyline, your score depends on the number of segments in the polyline (see the Scoring section below).

You do not need to submit any source code for this problem.

Input Format

Each input file has the following format:

• Line $1$: $n$.
• Line $1+i$ (here $1<i\le n$): $x_i\ y_i$.

Output Format

Each output file must follow the format below:

• Line $1$: $k$.
• Line $1+j$ (here $1\le j\le k$): $sx_j\ sy_j$.

Note that the second line should contain $sx_1$ and $sy_1$ (that is, the output must not include $sx_0$ and $sy_0$). All $sx_j$ and $sy_j$ must be integers.

4
2 1 
3 3
4 4
5 2

6
2 0
2 3
5 3
5 2
4 2
4 4

Hint

Sample explanation

This sample is not from any of the actual testdata; it is only meant to help you understand the statement.

The output shown is also only one possible output.

Constraints

• $1\le n\le 10^5$.
• $1\le x_i,y_i\le 10^9$.
• All values of $x_i$ and $y_i$ are integers.
• There are no two small dots with the same $x$ coordinate or the same $y$ coordinate, i.e., for all $i_1\not=i_2$, we have $x_{i_1}\not=x_{i_2}$ and $y_{i_1}\not=y_{i_2}$.
• $-2\times 10^9\le sx_i,sy_j\le 2\times 10^9$.
• The size of each submitted file (whether an output file or a compressed file) must not exceed $\text{15MB}$.

Scoring

For each test case, you can score at most $10$ points. If you output an invalid polyline, you will get $0$ points. Otherwise, your score is computed using a decreasing sequence $c_1, \cdots, c_{10}$.

Suppose your solution is a valid polyline with $k$ segments. Then you will get:

• $i$ points, if $k=c_i$ ($1 \le i \le 10$).
• $i+\dfrac{c_i-k}{c_i-c_{i+1}}$ points, if $c_{i+1} < k < c_i$ ($1 \le i \le 9$).
• $0$ points, if $k > c_1$.
• $10$ points, if $k < c_{10}$.

This can be understood as follows: on the interval $k \in (c_{i+1}, c_i)$, your score increases linearly as $k$ decreases. Once you score, the score is guaranteed to be within $[1, 10]$.

Below is the information about $n$ and $c_i$ for each test case:

Visualization tool

In the additional files for this problem, there is a script that can visualize the input files and output files.

To visualize an input file, use the following command:

python vis.py [input file]

For a given input, you can also visualize your solution with the command below. Due to technical limitations, the visualization tool only shows the first $1000$ segments in the output file.

python vis.py [input file] --solution [output file]

For example:

python vis.py examples/00.in --solution examples/00.out

Translated by ChatGPT 5