# PARTIEL BUG # """ idée de l'algo: 1. on trouve le point du polygone (n+1) le plus proche du point actuel (n) et de l'arrivée. 2. on le rajoute au tracé existant (1, 2, ... n+1) 3. on regarde si on peut raccourcir le tracé existant en supprimant le point (n), sans intersection avec le polygone 4. on répète jusqu'à atteindre l'arrivée Problème: il faut aussi s'assurer qu'il ny aura pas de collision, même sans raccourcir. Exemple: • c /| / | / | / | • a | • b | / |/ • d si on est actuellement au point (a), on risque de prendre (b) sans se soucier de l'arête (c-d) """ from math import sqrt def dist(a, b) -> float: x1, y1 = a x2, y2 = b return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) def ccw(a, b, c): return (c[1]-a[1]) * (b[0]-a[0]) > (b[1]-a[1]) * (c[0]-a[0]) def intersect(a, b, c, d) -> bool: """ est-ce que les segments a-b et c-d se croisent ? """ return ccw(a, c, d) != ccw(b, c, d) and ccw(a, b, c) != ccw(a, b, d) def is_safe(pt1, pt2) -> bool: """ Est-ce que pt1-pt2 croise un des segments du polygone ? """ return not True in ( intersect(pts[j], pts[(j+1)%len(pts)], pt1, pt2) for j in range(len(pts)) ) n = int(input()) x_dep, y_dep = map(int, input().split()) x_arr, y_arr = map(int, input().split()) xi = list(map(int, input().split())) yi = list(map(int, input().split())) pts = [(xi[i], yi[i]) for i in range(n)] dep = x_dep, y_dep arr = x_arr, y_arr trajet = [dep] curr_pos = dep while curr_pos != arr: avail_pts = [ pt for pt in pts+[arr] if is_safe(curr_pos, pt) ] # points qui ne croisent pas # On trie par distance à la position actuelle et à l'arrivée avail_pts.sort(key=lambda x: dist(curr_pos, x)+dist(arr, x)) new_pos = avail_pts[0] if avail_pts[0] != arr: pts.remove(avail_pts[0]) # on peut gagner un peu de temps ? if len(trajet) > 1 and is_safe(trajet[-2], new_pos): # On peut retirer l'élément cur_pos del trajet[-1] trajet.append(new_pos) curr_pos = new_pos print(sum((dist(trajet[i], trajet[i+1]) for i in range(len(trajet)-1))))