A5889. 「IOI2019」折线 Part. 1
编程题
NOI/NOI+/CTSC
知识点
题目描述
**此题负责评测原题的前 $7$ 个测试点。要评测后 $3$ 个测试点，请前往 [3181](https://loj.ac/problem/3181)。**
阿塞拜疆因地毯而闻名。作为一位地毯设计大师，你在做新设计时想画一条**折线**。一条折线是二维平面上包含 $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$ 个输入文件，这些文件给出了小圆点的位置。对每个输入文件，你需要提交一个答案文件，描述满足要求的折线。你的得分将取决于折线中的**线段数量**（参见下面的计分方式一节）。
阿塞拜疆因地毯而闻名。作为一位地毯设计大师，你在做新设计时想画一条**折线**。一条折线是二维平面上包含 $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$ 个小圆点的坐标。
第 $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$
第 $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
4 2 1 3 3 4 4 5 2
输出 #1
6 2 0 2 3 5 3 5 2 4 2 4 4
说明/提示
#### 数据范围与限制
对于所有数据：
- $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}$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$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$|$100\ 000$|$200\ 000$|$150\ 475$|$100\ 949$|$100\ 500$|$100\ 275$|$100\ 050$|$100\ 027$|$100\ 015$|$100\ 009$|$100\ 003$|
**再次提醒，此题负责评测原题的前 $7$ 个测试点。**
### 可视化工具
在本题的附加文件中有一个脚本，能让你对输入文件和输出文件进行可视化。
在对输入文件做可视化时，使用如下命令：
```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
```
对于所有数据：
- $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}$|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$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$|$100\ 000$|$200\ 000$|$150\ 475$|$100\ 949$|$100\ 500$|$100\ 275$|$100\ 050$|$100\ 027$|$100\ 015$|$100\ 009$|$100\ 003$|
**再次提醒，此题负责评测原题的前 $7$ 个测试点。**
### 可视化工具
在本题的附加文件中有一个脚本，能让你对输入文件和输出文件进行可视化。
在对输入文件做可视化时，使用如下命令：
```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
```