← 返回题目列表

AtCoder · maximum_2013_d

D. 情人比羁绊更重要

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

問題

E君是一年级生。他立志考入国立医科大学,每天勤奋学习。 今年夏天,他打算去补习学校,希望至少能提高一些成绩。 但是,他却有一个严重的问题,影响了他的学习。 那就是他的几位女性熟人各自都想单独带他出去约会。

与C小姐是青梅竹马的关系。她喜欢肉类料理,经常吃E君做的手料理,每天都紧紧依赖E君,说“最喜欢你”“爱你”。 与M小姐则是假装情侣的关系。她非常漂亮,因为有时会吸引不好的男性,所以通过让E君成为她的男朋友来驱赶那些不良的人。 与H小姐是前辈与后辈的关系。虽然她有些宅,但对E君非常积极,因为他们喜欢相同的漫画和动漫动作。 与—小姐在小时候有过约定的关系。她珍藏着幼儿园时的“结婚申请书”,经常以各种理由强迫E君结婚。

如果只和一个人去的话,之后会和没去的每个女生约会,结果他的学习时间会进一步减少。

他是恋爱贼。一直认为学生对恋爱这种事上心是不可饶恕的。 听说过去的一天里,有一位传说中的英雄Mr. TOKOSHI把人生都花在和女生约会上,但那是绝对不行的。

当我观察他们的行为时,我发现如果他们和一个人关系亲密,他们就会带我出去约会。 另一方面,人们发现,当两个或两个以上的人距离很近时,他们会互相控制,不会被带走。 而且,根据《女士协议》,她似乎不会被带到家和补习班半径50m的范围内。 利用这一点,E先生决定去读预科学校,而不是被带去约会。 在某些情况下,去补习班的路上可能会建有房屋, 我没有漂亮的靴子来跳过建筑物,所以 即使在你吃拉面的时候我不得不打扰你,我也无能为力。

我正准备去睡觉准备明天的补习班,突然遇到了一个问题。 我想离开家,这样补习班就不会迟到,但由于我走的是特殊路线,所以我无法使用常规路线搜索应用程序找到出行时间。 事实上,我无法决定设置闹钟的时间。 你的任务就是找到一条最短的路线让他去补习班而不被女孩们带走。 一旦知道了行驶的距离,E 先生就可以根据脚的速度计算出行驶时间。

入力

输入是按以下格式从标准输入给出的。
N
EX EY
SX SY
GX_1 GY_1
:
GX_N GY_N
  1. 第一行是一个整数 N 。
    • N 代表女孩的数量。
    • 0 ≦ N ≦ 20 得到保证。
  2. 第二行是一个整数 EX, EY 。
    • EX 是E君的 X 表示坐标。
    • EY 是E君的 Y 表示坐标。
    • -1,000 ≦ EX, EY ≦ 1,000 得到保证。
  3. 第三行是一个整数SX, SY。
    • SX 是一所预科学校 X 表示坐标。
    • SY 是一所预科学校 Y 表示坐标。
    • -1,000 ≦ SX,SY ≦ 1,000 得到保证。
  4. 从第 4 行开始 N+3 至行 在 N 行中,女孩位置的整数 GX_i, GY_i 由半角空格分隔。
    • GX_i 表示 i 第一个女孩的 X 表示坐标。
    • GY_i 表示 i 第一个女孩的 Y 表示坐标。
    • -1,000 ≦ GX_i, GY_i ≦ 1,000 得到保证。
  5. 所有位置均以米为单位。
  6. 保证E家和女生地点、补习班和女生地点、女生地点都不一样。

出力

输出一条线路上补习班的最短路线的行驶距离。
如果路由不存在 只需输出 impossible 。
即使行驶距离超过 10,000 impossible 。
输出数量如果不超过10,000,则有绝对误差。 10^{-6} 或更少是可以接受的。
真正的最短行驶距离是 即使超过 10,000 - 10^{-6} 只允许输出 impossible 。

入力例

4
0 0
110 10
50 -10
50 10
60 0
60 20

出力例

114.142135623731
  • 最好走下面所示的路线。 排序得到的序列