from math import sqrt from collections.abc import Mapping from typing import TypeVar, Optional, Iterator, Generic T = TypeVar("T") class Graph(Mapping, Generic[T]): """Non oriented graph""" def __init__(self) -> None: self._edges: dict = {} def __str__(self) -> str: return "\n".join( (f"{key} -> {self._edges[key]}" for key in self._edges) ) def __len__(self) -> int: return len(self._edges) def __getitem__(self, e) -> list[tuple[T, int]]: return self._edges[e] def __iter__(self) -> Iterator[object]: return iter(self._edges) def __contains__(self, item: object) -> bool: return item in self._edges.keys() def add_node(self, u: T) -> None: if u in self._edges.keys(): raise IndexError self._edges[u] = set() def add_edge(self, source: T, target: T, weight=None) -> None: if source not in self._edges: self.add_node(source) if target not in self._edges: self.add_node(target) if weight is None: weight = 1 self._edges[source].add((target, weight)) self._edges[target].add((source, weight)) def dijkstra(self, start: T, stop: T) -> int: distances: Dict[T, int] = {node: float('inf') for node in self._edges} distances[start] = 0 unvisited: Set[T] = set(self._edges) while unvisited: current_node = min(unvisited, key=lambda node: distances[node]) if current_node == stop: return distances[stop] unvisited.remove(current_node) for neighbor, weight in self._edges[current_node]: alternative_route = distances[current_node] + weight if alternative_route < distances[neighbor]: distances[neighbor] = alternative_route return -1 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 g = Graph() for pt in pts: g.add_node(pt) g.add_node(dep) g.add_node(arr) for pt1 in g: for pt2 in g: if is_safe(pt1, pt2): g.add_edge(pt1, pt2, weight=dist(pt1, pt2)) print(g.dijkstra(dep, arr))