#P1362. 种花
种花
【问题描述】
植物大战僵尸这款游戏中,还有个特别有意思的赚钱方式——种花(能长金币的花)。
种出来的金币需要玩家点击才能得到,或者,玩家可以购买一只蜗牛来帮助捡金币。然而,蜗牛爬得慢是众所周知的。所以,场上有若干金币时,蜗牛总是喜欢以最少的行 程来捡走所有的金币。
现在告诉你场上n个金币所在位置的坐标,以及蜗牛所在位置,让你求出蜗牛捡走所有金币的最小行程。
【输入数据】
第一行一个正整数n,表示金币数量
之后n行,每行两个非负整数x、y,分别表示金币所在位置坐标
最后一行两个正整数x、y表示蜗牛起始位置。
【输出数据】
一个实数(保留2位小数),表示最短行程
【输入样例】
4
0 1
1 1
1 0
2 2
0 0
【输出样例】
4.83
说明:
(0,0)→(1,0)→(0,1)→(1,1)→(2,2)
1 + 1.414 + 1 + 1.414 = 4.83
【数据范围】
对于20%的数据,n=3
对于70%的数据,n<=8
对于100%的数据,n<=16 x、y<=10000