Cannot parse: undefinedms error parsing time

题目描述

此题负责评测原题的后 $3$ 个测试点。要评测前 $7$ 个测试点，请前往 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$

4
2 1
3 3
4 4
5 2

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}$
$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$ 个测试点。

可视化工具

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

在对输入文件做可视化时，使用如下命令：

python vis.py [input file]

对于某个输入数据，你还可以使用下面的命令对你的解答进行可视化，由于技术方面的限制，所提供的可视化工具仅显示输出文件中的前 $1000$ 条线段。

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

例如：

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