Геометрическая карта
Ваша задача — разработать программу, которая определяет кратчайший путь между двумя заданными точками на карте улиц, представленной в виде набора отрезков на плоскости.
Рисунок 1: Пример карты
На Рисунке 1 показана карта улиц, где некоторые отрезки обозначают улицы, а другие — знаки, указывающие направления, в которых движение запрещено. Например, AE, AM, MQ, EQ, CP и HJ — это улицы, а остальные — знаки. Обычно один конец знака касается только одного отрезка улицы, а другой конец остаётся свободным. Каждая конечная точка улицы может соприкасаться с одной или несколькими улицами, но не со знаками.
Знак BF, например, указывает, что в точке B движение возможно только слева направо. В общем случае, движение с тупого угла на острый в точке, где знак касается улицы, запрещено (например, угол CBF тупой, а угол ABF острый). Нельзя двигаться напрямую ни из P в M, ни из M в P, так как движение слева направо не проходит через N, а справа налево — через O. В случае, когда угол между знаком и улицей прямой, движение в любом направлении в этой точке невозможно. Например, движение между H и J в обоих направлениях запрещено.
Ваша программа должна находить кратчайший путь, соблюдая эти правила дорожного движения. Длина отрезка между (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, если пути от начальной точки до конечной не существует.