#P9239. 「IOI2019」折线 Part. 2
「IOI2019」折线 Part. 2
「IOI2019」折线 Part. 2
Hydro 提交说明
本题保持提交答案题形式。请下载附件中的固定输入,在本地生成答案,然后把以下文件放在 ZIP 根目录提交:
08.out, 09.out, 10.out。
评测会解压对应答案文件并运行专用评分器;不提交 C++ 源代码。
| 输入 | 提交的输出文件 |
|---|---|
| 08.in | 08.out |
| 09.in | 09.out |
| 10.in | 10.out |
本 OJ 三点满分依次为 33、33、34,总分 100;下文原赛每点 10 分的比例保持不变。每份输出使用至多 100003 条合法线段即可得该点满分。首行是线段数,不能与原始点数 100000 作文本比较。
题目描述
阿塞拜疆因地毯而闻名。作为一位地毯设计大师,你在做新设计时想画一条折线。一条折线是二维平面上包含 条线段的线段序列,而这些线段由包含 个点 的点序列按照此规则构成:对所有的 ,都有一条线段连接点 和 。
为完成这个新设计,你已经标出了二维平面中的 个小圆点。小圆点 ()的坐标为 。不存在 坐标或 坐标相同的两个小圆点。
现在你想要找到一个点序列 $(sx[0], sy[0]),(sx[1],sy[1]), \cdots, (sx[k], sy[k])$,由该点序列构成的折线需满足
- 该折线从 开始(即 且 )。
- 该折线经过所有的小圆点(它们不必是线段的端点)。
- 该折线仅包括水平线段和竖直线段(对于构成该折线的连续两个点,其 坐标或 坐标相等)。
折线中的线段可以相交或重叠;换言之,平面上的每个点可以被任意数量的线段覆盖。
本题是一个有部分分的提交答案型题目。请从上方「附加文件」下载 个输入文件,这些文件给出了小圆点的位置。对每个输入文件,你需要提交一个答案文件,描述满足要求的折线。你的得分将取决于折线中的线段数量(参见下面的计分方式一节)。
输入格式
第一行,一个整数 ,表示小圆点的数量。
第 行(),两个整数 ,表示第 个小圆点的坐标。
输出格式
第一行,一个整数 ,表示在折线中你使用的线段数量。
第 行(),两个整数 ,表示你选取的点序列中第 个点的坐标。
注意:
- 你不需要输出 ;换言之,第 行输出的是 。
- 都必须为整数。
样例

4
2 1
3 3
4 4
5 2
6
2 0
2 3
5 3
5 2
4 2
4 4
数据范围与提示
数据范围与限制
对于所有数据:
- 所有 和 和值都是整数。
- 不存在 坐标或 坐标相同的两个小圆点,也就是说,对于所有的 ,都有 ,且 。
计分方式
对每个测试点,你最多能够得到 分,如果给出一条非法的折线,你将得到 分。否则,得分将根据一个递减序列 来计算。
假设你的解答是一条包含 条线段的合法折线。那么,你将得到
- 分,如果 ()
- 分,如果 ()
- 分,如果
- 分,如果 。
可以这样理解:在 这个区间上,你的得分是随着 减小线性增大的。一旦得分,得分一定在 区间内。
以下是每个测试点 与 的信息:
| 测试点 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
再次提醒,此题负责评测原题的后 个测试点。
可视化工具
可下载 vis.py,它,能让你对输入文件和输出文件进行可视化。
在对输入文件做可视化时,使用如下命令:
python vis.py [input file]
对于某个输入数据,你还可以使用下面的命令对你的解答进行可视化,由于技术方面的限制,所提供的可视化工具仅显示输出文件中的前 条线段。
python vis.py [input file] --solution [output file]
例如:
python vis.py examples/00.in --solution examples/00.out