(每个测试点1s)

背景

PLQ is a clever boy.一天,他到郊外散步,突然进入了一个神秘的山谷,山谷的平地上有n个洞,洞中似乎有些什么。这时,一个老人出现了,他笑道:PLQ,这几个洞中藏着一个宝藏,是古代君王留下的,目的是奖赏后来的勤劳勇敢的人。不过顺着这些洞一个一个找可是很难找到宝藏的,因为古代的聪明人设置了一个机关,一个人只有寻找宝藏失败k次之后,这个宝藏的入口才会出现,当然,你可以重复寻找(比如你去了第一个洞寻找,接下来去第二个洞寻找,然后还可以回到第一个洞寻找,这样如果没找到宝藏,则视为失败了3次,如果第k次失败寻找正好在藏有宝藏的洞中,则还需去另一个洞中寻找一次,宝藏才会出现,一直呆在同一个山洞中(或连续在同一个洞中寻找)只视为寻找了一次)。

PLQ想要许许多多的mz,正和其意,但这些洞相距还是很远的。于是他又开始琢磨了,宝藏会出现在哪个洞中呢?他仔细观察,其他的洞入口都比较明亮,只有第a个洞看起来十分黑暗。嗯,宝藏一定会出现在这个洞里。PLQ可是没吃晚饭就跑出来的,于是他想找到一条最短的寻找路线,以节省体力,找到这个宝藏。

描述

给出每个洞的坐标,两个洞之间的距离为直线距离S(S2=(a1-a2)2+(b1-b2)2),其中(a1,b1)为一个洞的坐标,(a2,b2)为另一个洞的坐标。同时给出PLQ的初始坐标(X0,Y0),求出最短的寻找路径的长度(洞中的路径忽略不计),输入数据保证每个洞坐标和PLQ的坐标互不相同。

输入格式

输入包括n+1行,第一行有5个用空格隔开的整数n,a,k,X0,Y0。接下来的n行,每行有两个用空格隔开的整数,第i行为xi和yi,表示第i个山洞的坐标。

输出格式

输出只有一个实数,为最短的寻找路径长度(保留两位小数)。

样例输入

4 4 2 1 1

2 2

3 3

3 4

4 4

样例输出

4.24

数据范围与约定

  • 100%的数据,0<n≤100,1≤a≤n,1≤k≤200,-10000≤X0,Y0,Xi,Yi≤10000。

来源

原创