P7195 [IOI 2019] Polyline

You can download the [input files](https://cowtransfer.com/s/9b9c30ef6dc74d) here.

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.

Each input file has the following format: - Line $1$: $n$. - Line $1+i$ (here $1

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.

#### 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: |Test case|$n$|$c_1$|$c_2$|$c_3$|$c_4$|$c_5$|$c_6$|$c_7$|$c_8$|$c_9$|$c_{10}$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$20$|$50$|$45$|$40$|$37$|$35$|$33$|$28$|$26$|$25$|$23$| |$2$|$600$|$1\ 200$|$937$|$674$|$651$|$640$|$628$|$616$|$610$|$607$|$603$| |$3$|$5\ 000$|$10\ 000$|$7\ 607$|$5\ 213$|$5\ 125$|$5\ 081$|$5\ 037$|$5\ 020$|$5\ 012$|$5\ 008$|$5\ 003$| |$4$|$50\ 000$|$100 \ 000$|$75\ 336$|$50\ 671$|$50\ 359$|$50\ 203$|$50\ 047$|$50\ 025$|$50\ 014$|$50\ 009$|$50\ 003$| |$5$|$72\ 018$|$144\ 036$|$108\ 430$|$72\ 824$|$72\ 446$|$72\ 257$|$72\ 067$|$72\ 044$|$72\ 033$|$72\ 027$|$72\ 021$| |$6$|$91\ 891$|$183\ 782$|$138\ 292$|$92\ 801$|$92\ 371$|$92\ 156$|$91\ 941$|$91\ 918$|$91\ 906$|$91\ 900$|$91\ 894$| |$7$|$10^5$|$2\times 10^5$|$150\ 475$|$100\ 949$|$100\ 500$|$100\ 275$|$100\ 050$|$100\ 027$|$100\ 015$|$100\ 009$|$100\ 003$| #### 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: ```plain 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. ```plain python vis.py [input file] --solution [output file] ``` For example: ```plain python vis.py examples/00.in --solution examples/00.out ``` Translated by ChatGPT 5