A5885. 「IOI2019」折线 Part. 2

**此题负责评测原题的后 $3$ 个测试点。要评测前 $7$ 个测试点，请前往 [3178](https://loj.ac/problem/3178)。**

阿塞拜疆因地毯而闻名。作为一位地毯设计大师，你在做新设计时想画一条**折线**。一条折线是二维平面上包含 $t$ 条线段的线段序列，而这些线段由包含 $t+1$ 个点 $p_0, \cdots p_t$ 的点序列按照此规则构成：对所有的 $0 \le j \le t-1$，都有一条线段连接点 $p_j$ 和 $p_{j+1}$。

为完成这个新设计，你已经标出了二维平面中的 $n$ 个**小圆点**。小圆点 $i$（$1 \le i \le n$）的坐标为 $(x[i], y[i])$。**不存在 $x$ 坐标或 $y$ 坐标相同的两个小圆点。**

现在你想要找到一个点序列 $(sx[0], sy[0]),(sx[1],sy[1]), \cdots, (sx[k], sy[k])$，由该点序列构成的折线需满足
- 该折线从 $(0, 0)$ 开始（即 $sx[0]=0$ 且 $sy[0] = 0$）。
- 该折线经过所有的小圆点（**它们不必是线段的端点**）。
- 该折线仅包括水平线段和竖直线段（对于构成该折线的连续两个点，其 $x$ 坐标或 $y$ 坐标相等）。

折线中的线段可以相交或重叠；换言之，平面上的每个点可以被任意数量的线段覆盖。

本题是一个有部分分的**提交答案型**题目。请从上方「附加文件」下载 $10$ 个输入文件，这些文件给出了小圆点的位置。对每个输入文件，你需要提交一个答案文件，描述满足要求的折线。你的得分将取决于折线中的**线段数量**（参见下面的计分方式一节）。

第一行，一个整数 $n$，表示小圆点的数量。
第 $i+1$ 行（$1 \le i \le n$），两个整数 $x[i], y[i]$，表示第 $i$ 个小圆点的坐标。

第一行，一个整数 $k$，表示在折线中你使用的线段数量。
第 $j+1$ 行（$1 \le j \le k$），两个整数 $sx[j], sy[j]$，表示你选取的点序列中第 $j$ 个点的坐标。

注意：
- 你**不需要**输出 $sx[0], sy[0]$；换言之，第 $2$ 行输出的是 $sx[1], sy[1]$。
- $sx[j], sy[j]$ 都必须为整数。
- $-2 \cdot 10^9 \le sx[j], sy[j] \le 2 \cdot 10^9$

#### 数据范围与限制
对于所有数据：
- $1 \le n \le 100\ 000$
- $1 \le x[i], y[i] \le 10^9$
- 所有 $x[i]$ 和 $y[i]$ 和值都是整数。
- 不存在 $x$ 坐标或 $y$ 坐标相同的两个小圆点，也就是说，对于所有的 $i_1 \neq i_2$，都有 $x[i_1] \neq x[i_2]$，且 $y[i_1] \neq y[i_2]$。

#### 计分方式
对每个测试点，你最多能够得到 $10$ 分，如果给出一条非法的折线，你将得到 $0$ 分。否则，得分将根据一个递减序列 $c_1, \cdots, c_{10}$ 来计算。

假设你的解答是一条包含 $k$ 条线段的合法折线。那么，你将得到
- $i$ 分，如果 $k=c_i$（$1 \le i \le 10$）
- $i+\dfrac{c_i-k}{c_i-c_{i+1}}$ 分，如果 $c_{i+1} < k < c_i$（$1 \le i \le 9$）
- $0$ 分，如果 $k > c_1$
- $10$ 分，如果 $k < c_{10}$。

可以这样理解：在 $k \in (c_{i+1}, c_i)$ 这个区间上，你的得分是随着 $k$ 减小线性增大的。一旦得分，得分一定在 $[1, 10]$ 区间内。

以下是每个测试点 $n$ 与 $c_i$ 的信息：

|测试点|$n$|$c_1$|$c_2$|$c_3$|$c_4$|$c_5$|$c_6$|$c_7$|$c_8$|$c_9$|$c_{10}$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$8 \sim 10$|$100\ 000$|$200\ 000$|$150\ 475$|$100\ 949$|$100\ 500$|$100\ 275$|$100\ 050$|$100\ 027$|$100\ 015$|$100\ 009$|$100\ 003$|

**再次提醒，此题负责评测原题的后 $3$ 个测试点。**

### 可视化工具
在本题的附加文件中有一个脚本，能让你对输入文件和输出文件进行可视化。

在对输入文件做可视化时，使用如下命令：
```plain
python vis.py [input file]
```

对于某个输入数据，你还可以使用下面的命令对你的解答进行可视化，由于技术方面的限制，所提供的可视化工具仅显示输出文件中的**前 $1000$ 条线段**。
```plain
python vis.py [input file] --solution [output file]
```

例如：
```plain
python vis.py examples/00.in --solution examples/00.out
```