Геометрична Карта
Ваше завдання — розробити програму, яка визначає найкоротший шлях між двома заданими точками на карті вулиць, представленій у вигляді набору відрізків на площині.
Рисунок 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_2, y_2) є .
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких має наступний формат.
n
x_s y_s
x_g y_g
x^1_1 y^1_1 x^1_2 y^1_2
...
x^k_1 y^k_1 x^k_2 y^k_2
...
x^n_1 y^n_1 x^n_2 y^n_2
n — це кількість відрізків, і це додатне ціле число, менше або рівне 200.
(x_s, y_s) і (x_g, y_g) — це початкова і кінцева точки відповідно. Ви можете припустити, що (x_s, y_s) ≠ (x_g, y_g) і що кожна з них розташована на кінцевій точці якогось відрізка, що представляє вулицю. Ви також можете припустити, що найкоротший шлях від (x_s, y_s) до (x_g, y_g) є унікальним.
(x^k_1, y^k_1) і (x^k_2, y^k_2) — це дві кінцеві точки k-го відрізка. Ви можете припустити, що (x^k_1, y^k_1) ≠ (x^k_2, y^k_2). Два відрізки ніколи не перетинаються і не перекриваються. Тобто, якщо вони мають спільну точку, це завжди одна з їх кінцевих точок.
Всі координати є невід'ємними цілими числами, меншими або рівними 1000. Кінець вводу позначається рядком, що містить один нуль.
Вихідні дані
Для кожного набору даних на вході виведіть кожну точку перетину вулиць на найкоротшому шляху від початкової точки до кінцевої, по одній в рядок виходу в цьому порядку, і нуль у рядку після цих точок. Зверніть увагу, що точка перетину вулиць — це точка, де зустрічаються принаймні два відрізки, що представляють вулиці. Рядок виходу для точки перетину вулиць повинен містити її x та y-координати, розділені пробілом.
Виведіть −1, якщо немає шляхів від початкової точки до кінцевої.