Геометрична Карта#5830

Геометрична Карта

5 секунд

64 мегабайти

Легка

Ваше завдання — написати програму, яка знаходить найкоротший шлях між двома заданими точками на карті вулиць, представленій у вигляді набору відрізків на площині.

Рисунок 1: Приклад карти

На Рисунку 1 зображена карта вулиць, де деякі відрізки є вулицями, а інші — знаками, що показують напрямки, у яких автомобілі не можуть рухатись. Зокрема, AE, AM, MQ, EQ, CP та HJ є вулицями, інші — знаки. Зазвичай одна кінцева точка знака торкається лише одного відрізка, що представляє вулицю, а інша кінцева точка є відкритою. Кожна кінцева точка кожної вулиці торкається однієї або більше вулиць, але не знаків.

Знак BF, наприклад, вказує, що в точці B автомобілі можуть рухатись зліва направо, але не в зворотному напрямку. Загалом, автомобілі не можуть рухатись з боку тупого кута до боку гострого кута в точці, де знак торкається вулиці (наприклад, кут CBF тупий, а кут ABF гострий). Автомобілі не можуть рухатись безпосередньо ні з P до M, ні з M до P, оскільки ті, хто рухається зліва направо, не можуть пройти через N, а ті, що рухаються справа наліво, — не можуть пройти через O. У випадку, коли кут між знаком і вулицею є прямим, автомобілі не можуть рухатись у жодному напрямку у цій точці. Наприклад, автомобілі не можуть рухатись безпосередньо ні з H до J, ні з J до H.

Ваша програма повинна знаходити найкоротший шлях, дотримуючись цих правил дорожнього руху. Довжина відрізка між $(x_{1}, y_{1})$ (x_1, y_1) і $(x_{2}, y_{2})$ (x_2, y_2) визначається як звичайна евклідова відстань.

Вхідні дані

Вхідні дані складаються з декількох наборів, кожен з яких має наступний формат:

$n$

$x_{s} y_{s}$ x_s~y_s

$x_{g} y_{g}$ x_g~y_g

$x_{1}^{1} y_{1}^{1} x_{2}^{1} y_{2}^{1}$ x^1_1~y^1_1~x^1_2~y^1_2

...

$x_{1}^{k} y_{1}^{k} x_{2}^{k} y_{2}^{k}$ x^k_1~y^k_1~x^k_2~y^k_2

...

$x_{1}^{n} y_{1}^{n} x_{2}^{n} y_{2}^{n}$ x^n_1~y^n_1~x^n_2~y^n_2

$n$ — кількість відрізків, додатне ціле число, не більше $200$ .

$(x_{s}, y_{s})$ (x_s, y_s) та $(x_{g}, y_{g})$ (x_g, y_g) — це початкова і кінцева точки відповідно. Припускається, що $(x_{s}, y_{s}) \neq = (x_{g}, y_{g})$ (x_s, y_s) \neq (x_g, y_g), і кожна з них розташована в кінцевій точці деякого відрізка, який представляє вулицю. Також гарантується, що найкоротший шлях від $(x_{s}, y_{s})$ (x_s, y_s) до $(x_{g}, y_{g})$ (x_g, y_g) є єдиним.

$(x_{1}^{k}, y_{1}^{k})$ (x^k_1, y^k_1) та $(x_{2}^{k}, y_{2}^{k})$ (x^k_2, y^k_2) — це дві кінцеві точки $k$ -го відрізка. Припускається, що $(x_{1}^{k}, y_{1}^{k}) \neq = (x_{2}^{k}, y_{2}^{k})$ (x^k_1, y^k_1) \neq (x^k_2, y^k_2). Два відрізки ніколи не перетинаються та не перекриваються, окрім, можливо, кінців; якщо вони мають спільну точку, це завжди одна з їхніх кінцевих точок.

Усі координати — невід’ємні цілі числа, не більші $1000$ . Кінець вводу позначається рядком із одним нулем.

Вихідні дані

Для кожного набору даних на вході виведіть кожну точку перетину вулиць на найкоротшому шляху від початкової до кінцевої точки, по одній в рядок у цьому порядку, потім рядок з одним нулем. Точка перетину вулиць — це точка, де зустрічаються принаймні два відрізки, що представляють вулиці. Кожний рядок для точки перетину має містити її $x$ - та $y$ -координати, розділені пробілом.

Виведіть $- 1$ , якщо немає шляху від початкової до кінцевої точки.

Приклади

Приклад 1