import heapq
import sys
import math
sys.setrecursionlimit(10000)
INF = 0x3f3f3f3f
## 定义类
class Point:
def __init__(self, x, y):
self.x = float(x)
self.y = float(y)
# 计算欧式距离
def get_distance(p1, p2):
return math.sqrt(abs(p1.x - p2.x) ** 2 + abs(p1.y - p2.y) ** 2)
def dijkstra(G, start, endp):
dis = dict((point, INF) for point in G)
dis[start] = 0.00
vis = dict((point, False) for point in G)
# heap
pq = []
heapq.heappush(pq, [dis[start], start])
path = dict((point, [start]) for point in G)
while len(pq) > 0:
v_dis, v = heapq.heappop(pq)
if vis[v] == True:
continue
vis[v] = True
p = path[v].copy()
for point in G:
distance = get_distance(v, point)
if distance > 100.00:
continue
new_dis = dis[v] + distance
if new_dis < dis[point] and (not vis[point]):
dis[point] = new_dis
heapq.heappush(pq, [dis[point], point])
temp = p.copy()
temp.append(point)
path[point] = temp
distance = dis[endp]
if distance == INF:
print("-1")
else:
print("{:.2f}".format(distance))
while True:
try:
numbers = input().strip().split(",") # 根据','进行分割
limit = int(numbers[0])
point_list = []
numbers = list(map(float, numbers))
stap = Point(numbers[1], numbers[2])
endp = Point(numbers[-2], numbers[-1])
if stap.x > limit or stap.y > limit or stap.x < 0 or stap.y < 0:
print("-1")
elif endp.x > limit or endp.y > limit or endp.x < 0 or endp.y < 0:
print("-1")
else:
for i in range(1, len(numbers), 2):
if numbers[i] <= limit and numbers[i + 1] <= limit:
point_list.append(Point(numbers[i], numbers[i + 1]))
dijkstra(point_list, point_list[0], point_list[-1])
except EOFError:
break