UOJ Logo Universal Online Judge

UOJ

#536. 【IOI2019】折线

附件下载 统计

阿塞拜疆因地毯而闻名。作为一位地毯设计大师,你在做新设计时想画一条折线。一条折线是二维平面上包含 t 条线段的线段序列,而这些线段由包含 t+1 个点 p0,p1,,pn 的点序列按照此规则构成:对所有的 0i<n,都有一条线段连接点 pipi+1

为完成这个新设计,你已经标出了二维平面中的 n 个小圆点。小圆点 i 的坐标为 (xi,yi)。不存在 x 坐标或 y 坐标相同的两个小圆点。

现在你想要找到一个点序列 (sx0,sy0),(sx1,sy1),,(sx2,sy2),由该点序列构成的折线需满足

  • 该折线从 (0,0) 开始(即 sx0=sy0=0 )。
  • 该折线经过所有的小圆点(它们不必是线段的端点)。
  • 该折线仅包括水平线段和竖直线段(对于构成该折线的连续两个点,其 x 坐标或 y 坐标相等,且不重合)。
  • 折线中的线段可以相交或重叠;换言之,平面上的每个点可以被任意数量的线段覆盖。

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

输入格式

这是一道提交答案题,共有 10 组输入数据,这些数据命名为 a1.in ~ a10.in

第一行,一个整数 n,表示小圆点的数量。

接下来 n 行,每行两个整数xi,yi,表示第 i 个小圆点的坐标。

输出格式

对于每组输入数据,你需要提交相应的输出文件 a1.out ~ a10.out

第一行,一个整数 t,表示在折线中你使用的线段数量。

接下来 t 行,每行两个整数 (sxi,syi) ,第 i 行表示你选取的点序列中第 i 个点的坐标。

你的输出需要满足:

  • 2×109sxi,syi2×109

你不需要输出 (sx0,sy0)换言之,第 i+1 行输出的是 (sxi,syi)

样例一

input

4
2 1
3 3
4 4
5 2

output

2 0
2 3
5 3
5 2
4 2
4 4

explanation

样例一示意图

数据范围

计分方式

对每个测试点,你最多能够得到 10 分,

如果给出一条非法的折线,你将得到 0 分。否则,得分将根据一个递减序列 c1,,c10 来计算。

假设你的解答是一条包含 t 条线段的合法折线。那么,你将得到

  • i 分,如果 ci=t,(1i10)
  • i+citci+1ci 分,如果 ci+1<t<ci(1i9)
  • 0 分,如果 t>c1
  • 10 分,如果 t<c10

可以这样理解:在 k(ci+1,ci) 这个区间上,你的得分是随着 k 减小线性增大的。一旦得分,得分一定在 [1,10] 区间内。

由于某些计分方式的原因,OJ上每个测试点的得分为实际得分下取整得到的值。

以下是每个测试点 nci 的信息:

测试包编号nc1c2c3c4c5 c6c7c8c9c10
1205045403735 3328262523
26001200937674651640 628616610607603
35000100007607521351255081 50375020501250085003
45000010000075336506715035950203 5004750025500145000950003
572018144036108430728247244672257 7206772044720337202772021
691891183782138292928019237192156 9194191918919069190091894
710100000200000150475100949100500100275 100057100027100015100009100003

对于所有测试数据,满足 1n100000,109xi,yi109

输入数据下载

请上传你要提交的文件,并命名为 a1.out, a2.out, a3.out, a4.out, a5.out, a6.out, a7.out, a8.out, a9.out, a10.out。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: