Условие:
После исчезновения легендарного пилота Стига, мегакорпорация GearCore ищет нового участника
для секретной программы "Трасса-0". Вы — алгоритмист, а не гонщик,
но чтобы выжить, вам придётся пройти по всей трассе, не пропустив ни одного поворота.
И чем меньше вы будете поворачивать, тем больше шансов у вас вернуться живым.
Система безопасности требует, чтобы вы прошли по каждому участку трассы ровно один раз и вернулись в исходную точку.
Именно так выглядит эйлеров цикл.
❓ Задача
Вам дан трек — это граф с уникальными прямолинейными сегментами дорог.
Каждая дорога — это ребро между двумя узлами с координатами на плоскости.
Из каждой вершины выходит ровно 2 или 4 ребра, и гарантируется существование эйлерова цикла.
Ваша задача — найти эйлеров цикл, при котором суммарный угол поворота минимален.
Считать поворотом переход от одного ребра к другому при посещении узла.
Поворот измеряется в радианах, прямое продолжение считается поворотом в 0.
Входные данные
Первая строка: два числа — N и M
3 ≤ N ≤ 104 — количество узлов (вершин),
N ≤ M ≤ 2N — количество дорог (рёбер).
Следующие N строк: координаты узлов
Каждая строка: два целых числа x, y (
0
≤
x
,
y
≤
1
0
4
0≤x,y≤10
4
).
Все координаты уникальны.
Следующие M строк: описание дорог
Каждая строка: два числа i и j (
0
≤
i
,
j
<
N
0≤i,j<N) — дорога между узлами i и j.
Выходные данные
Ответ должен содержать одно число —
минимально возможную сумму поворотов на всём маршруте,
измеренную в радианах.
Погрешность при сравнении: не более
1
0
−
6
10
−6
.