← 返回题目列表

AtCoder · tenka1_2013_qualB_e

E. 天下一最短路线

中文机器翻译题面 查看原题

問題文

你是天下最短路竞赛的运营者。
天下最短路竞赛将按照如下规则举办。

  • 在二维平面上 N ( 1 ≦ N ≦ 100) 个点 p_i ( 1 ≦ i ≦ N ) 被给出
    • 点 p_i 的x 坐标是 x_i 在 y 坐标是 y_i 是
    • 点的数量 N 最大为 100 个
    • 每个坐标的值 x_i, y_i 全部 10,000 以下的非负整数
    • 所有点的坐标都不同。也就是说,i ≠ j 时,(x_i,\ y_i) ≠ (x_j,\ y_j) 满足
  • p_1 从开始点开始,输出经过所有点的路径
  • 路径长度最短的人获胜

高桥君打算参加天下一最短路竞赛,但他觉得无法战胜他的竞争对手、KLab的超级程序员拓也君。拓也君的程序是作为开源软件公开的,所以他打算通过改造这个程序来在比赛中获胜。

拓也君的程序如下。

  • 首先选择一个点 p_1 在还有未选择的点时,按以下步骤选择点
    • 从最后选择的点中,选择距离最近的未选择的点
    • 如果有多个最近的点,则选择其中ID最小的那个(点 p_i 的id是 i )
  • 按选取的顺序用线段连接,并将其作为路径输出

这个程序被高桥君改造后的结果如下。

  • 首先选择一个点 p_1 在还有未选择的点时,按以下步骤选择点
    • 还有未选取的点 3 如果存在一个或多个,最后选取的点开始 2 选择第n近的点
      • 此时,最接近的点与最后选取的点 2 个最近点的线段上,也不认为该点已被选中。
    • 还有未选取的点 2 如果少于一个,则选择距离最后一个选定点最近的点。
      • 从最后一个点中选择最近的点 不是 1 次, 请注意 2 次
    • 如果有多个距离相同的点,id越小,点越近。
  • 按选取的顺序用线段连接,并将其作为路径输出

这个 2 当我让两个程序相互竞争时,高桥在大多数情况下都会失败。然而,如果事情继续这样下去,我会为高桥感到难过,所以我决定只准备一个输入,让高桥留下平局或更好的结果。
您必须创建一个包含尽可能多顶点的数据集,这将为 Takahashi 带来平局或更好的结果。


入力

未给出任何输入。

出力

输出一个数据集,使 Takahashi 能够产生比平局更好的结果。输出采用以下格式。
N
x_1 y_1
x_2 y_2
:
x_N y_N

  1. 1行显示数据集中的顶点数。 输出为 N (1≦N≦100) 在 1 行
  2. 2线显示每个点。 x 座標 x_i、y 座標 y_i的,x_i y_i用空格分隔,N行 ( 0 ≦ x_i, y_i ≦ 10,000)
  3. 如果数据集满足条件, 您将获得N×2分。
两个程序的输出路径长度之间的绝对或相对差为 10^{-9}如果低于,则两个程序被视为平局。
也就是说,两个程序的输出路径长度分别为d_1, d_2当\frac{|d_1 - d_2|}{{\rm max}(1, d_1, d_2)} ≦ 10^{-9},视为平局。
另外,在输出末尾放置一个换行符。
预先计算并输出的结果可以按原样提交。在这种情况下,请选择 Text(cat) 作为要使用的语言并提交。

出力例 1

1
1 1
  • 重点是 1 ,两个程序输出的路径长度为 0 ,结果是平局。
  • 提交此输出: 2 可以获得积分

出力例 2

5
4 6
2 5
6 10
1 2
1 6
  • 拓也的程序要求的路线是 (4,6) → (2,5) → (1,6) → (1,2) → (6,10)这条路径的长度大约是17.084是
  • 図 1拓哉的程序路径
  • 高桥的程序要求的路线是 (4,6) → (1,6) → (1,2) → (2,5) → (6,10)这条路径的长度大约是16.565是
  • 図 2高桥的程序路径 您可以获得
  • 提交此输出: 10 积分