117 lines
2.9 KiB
Python
117 lines
2.9 KiB
Python
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)) |