阿塞拜疆因地毯而闻名。作为一位地毯设计大师，你在做新设计时想画一条折线。一条折线是二维平面上包含 $t$ 条线段的线段序列，而这些线段由包含 $t+1$ 个点 $p_0,p_1,\cdots,p_n$ 的点序列按照此规则构成：对所有的 $0 \le i < n$，都有一条线段连接点 $p_i$ 和 $p_{i+1}$。
为完成这个新设计，你已经标出了二维平面中的 $n$ 个小圆点。小圆点 $i$ 的坐标为 $(x_i,y_i)$。不存在 $x$ 坐标或 $y$ 坐标相同的两个小圆点。
现在你想要找到一个点序列 $(sx_0,sy_0),(sx_1,sy_1),\cdots,(sx_2,sy_2)$，由该点序列构成的折线需满足
- 该折线从 $(0,0)$ 开始（即 $sx_0=sy_0=0$ ）。
- 该折线经过所有的小圆点（它们不必是线段的端点）。
- 该折线仅包括水平线段和竖直线段（对于构成该折线的连续两个点，其 $x$ 坐标或 $y$ 坐标相等，且不重合）。
- 折线中的线段可以相交或重叠；换言之，平面上的每个点可以被任意数量的线段覆盖。
本题是一个有部分分的提交答案型题目。请从上方「附加文件」下载 $10$ 个输入文件，这些文件给出了小圆点的位置。对每个输入文件，你需要提交一个答案文件，描述满足要求的折线。你的得分将取决于折线中的线段数量（参见下面的计分方式一节）。
输入格式
这是一道提交答案题，共有 $10$ 组输入数据，这些数据命名为 a1.in ~ a10.in。
第一行，一个整数 $n$，表示小圆点的数量。
接下来 $n$ 行，每行两个整数$x_i,y_i$，表示第 $i$ 个小圆点的坐标。
输出格式
对于每组输入数据，你需要提交相应的输出文件 a1.out ~ a10.out。
第一行，一个整数 $t$，表示在折线中你使用的线段数量。
接下来 $t$ 行，每行两个整数 $(sx_i,sy_i)$ ,第 $i$ 行表示你选取的点序列中第 $i$ 个点的坐标。
你的输出需要满足:
- $-2\times 10^9 \le sx_i,sy_i \le 2 \times 10^9$。
你不需要输出 $(sx_0,sy_0)$换言之，第 $i+1$ 行输出的是 $(sx_i,sy_i)$。
样例一
input
4
2 1
3 3
4 4
5 2output
2 0
2 3
5 3
5 2
4 2
4 4explanation
数据范围
计分方式
对每个测试点，你最多能够得到 $10$ 分，
如果给出一条非法的折线，你将得到 $0$ 分。否则，得分将根据一个递减序列 $c_1,\cdots,c_{10}$ 来计算。
假设你的解答是一条包含 $t$ 条线段的合法折线。那么，你将得到
- $i$ 分，如果 $c_i=t,(1 \le i \le 10)$。
- $i+\frac{c_i-t}{c_{i+1}-c_i}$ 分，如果 $c_{i+1} < t < c_i(1 \le i \le 9)$。
- $0$ 分，如果 $t > c_1$。
- $10$ 分，如果 $t < c_{10}$。
可以这样理解：在 $k \in (c_{i+1},c_i)$ 这个区间上，你的得分是随着 $k$ 减小线性增大的。一旦得分，得分一定在 $[1,10]$ 区间内。
由于某些计分方式的原因，OJ上每个测试点的得分为实际得分下取整得到的值。
以下是每个测试点 $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$ | $1200$ | $937$ | $674$ | $651$ | $640$ | $628$ | $616$ | $610$ | $607$ | $603$ |
| $3$ | $5000$ | $10000$ | $7607$ | $5213$ | $5125$ | $5081$ | $5037$ | $5020$ | $5012$ | $5008$ | $5003$ |
| $4$ | $50000$ | $100000$ | $75336$ | $50671$ | $50359$ | $50203$ | $50047$ | $50025$ | $50014$ | $50009$ | $50003$ |
| $5$ | $72018$ | $144036$ | $108430$ | $72824$ | $72446$ | $72257$ | $72067$ | $72044$ | $72033$ | $72027$ | $72021$ |
| $6$ | $91891$ | $183782$ | $138292$ | $92801$ | $92371$ | $92156$ | $91941$ | $91918$ | $91906$ | $91900$ | $91894$ |
| $7 \sim 10$ | $100000$ | $200000$ | $150475$ | $100949$ | $100500$ | $100275$ | $100057$ | $100027$ | $100015$ | $100009$ | $100003$ |
对于所有测试数据，满足 $1 \le n \le 100000,-10^9 \le x_i,y_i \le 10^9$。
鄂公网安备 42010202000505 号