0397. Безопасный путь

Имя входного файла:	saferoute.in
Имя выходного файла:	saferoute.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Петя и Вася – хорошие друзья. Поэтому они часто ездят друг к другу в гости. Недавно Петя получил водительские права и собирается навестить своего друга. Для простоты будем считать, что все дороги в городе, в котором они живут, являются бесконечными прямыми. В месте пересечения двух или более дорог находятся перекрестки. Дома Пети и Васи расположены возле некоторых дорог города, но не на перекрестках.

Петя начинает путь на дороге возле своего дома. При этом он может выбрать любое из двух направлений. Когда Петя подъезжает к перекрестку, он может повернуть на любую другую проходящую через него дорогу или продолжить ехать по текущей. Поскольку Петя не очень опытный водитель, каждый поворот, который он совершает, заставляет его волноваться. Причем волнение Пети равно величине угла, на который он поворачивает, в градусах. Например, при повороте на прямой угол волнение Пети равно 90.

При менее крутом повороте Петя волнуется меньше, а при более крутом – сильнее.

Будем считать, что волнение Пети в течении всего маршрута равно сумме величин в градусах углов, на которые ему придется повернуть в течении движения. Конечно, Петя хочет воспользоваться маршрутом, который заставит его волноваться как можно меньше.

Помогите Пете выяснить, чему равно минимальное суммарное волнение, которое он испытает, добравшись до дома Васи.

Формат входного файла

В первой строке входного файла находится целое число n (1 ≤ n ≤ 50) – количество дорог в городе. В следующих n строках находится описание дорог.

Каждая дорога описывается четверкой целых чисел x₁, y₁, x₂, y₂, которые задают координатами двух различных точек (x₁, y₁) и (x₂, y₂), через которые проходит дорога.

Гарантируется, что никакие две дороги не совпадают. В следующих двух строках заданы координаты домов Пети и Васи. Гарантируется, что каждый дом находится ровно на одной дороге, а также, что Петя и Вася живут в разных местах.

Координаты всех точек во входном файле являются целыми числами и не превосходят 100 по абсолютному значению.

Формат выходного файла

В выходной файл выведите единственное число – суммарный угол в градусах, на который придется повернуть Пете при оптимальном выборе маршрута. Ответ считается правильным, если его относительная или абсолютная погрешность не превосходит 10^-9.

Если Петя никак не сможет добраться до дома Васи, выведите число -1.

Пример:

saferoute.in	saferoute.out
3 0 0 2 0 1 1 0 2 1 2 3 2 -3 0 3 2	270.0
1 0 0 2 0 0 0 2 0	0.0
5 0 0 1 0 0 0 1 1 0 0 0 1 0 0 -1 1 0 1 1 1 5 0 0 5	90.0

Следующий рисунок соответствует первому примеру. Петя совершает два поворота на 135 градусов, его суммарное волнение равно 270.

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение