도로 지도

어떤 도시의 도로 지도가 주어졌을 때, 주어진 두 점 사이의 최단 경로를 찾는 프로그램을 작성하시오.

도로 지도는 평면 위 선분들의 집합으로 표현된다. 어떤 선분은 도로를 나타내고, 나머지 선분은 어느 방향으로 갈 수 없는지를 나타내는 표지판이다. 어떤 선분의 두 끝점 중 정확히 한 끝점만 다른 선분 위에 놓여 있고 나머지 한 끝점은 그렇지 않다면, 그 선분은 표지판이다. 그 외의 모든 선분은 도로이다.

도로 위의 점 $B$에 붙은 표지판은 $B$를 지나는 이동을 제한한다. 도로가 $B$의 양쪽으로 점 $A$와 $C$를 지난다고 하고, $F$를 표지판의 (도로에 닿지 않은) 자유로운 끝점이라고 하자. 표지판과 도로가 이루는 각들 중에서, 둔각이 있는 쪽에서 예각이 있는 쪽으로는 이동할 수 없다. 예를 들어 각 $ABF$가 예각이고 각 $CBF$가 둔각이면, $A$에서 $B$를 지나 $C$로는 갈 수 있지만 $C$에서 $B$를 지나 $A$로는 갈 수 없다. 표지판이 도로와 직각을 이루면, $B$를 아예 지날 수 없다.

이 규칙을 지키면서 시작점에서 끝점으로 가는 최단 경로를 찾으시오. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

각 테스트 케이스의 첫째 줄에는 선분의 개수 $n$ ($1 \le n \le 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)$는 서로 다르고, 최단 경로는 항상 유일하다.

이어지는 $n$개의 줄에는 각 선분의 정보가 $x_{1k}\ y_{1k}\ x_{2k}\ y_{2k}$ 형식으로 주어지며, 이는 $k$번째 선분의 두 끝점이다. 한 선분의 두 끝점은 서로 다르고, 두 선분이 교차하는 경우는 없다. 즉, 선분은 항상 끝점에서만 만난다. 모든 좌표는 1000보다 작거나 같은 음이 아닌 정수이다.

각 테스트 케이스에 대해, 시작점에서 끝점으로 가는 최단 경로 위의 점들을 지나는 순서대로 출력한다. 먼저 시작점, 그다음 경로 위에서 도로가 둘 이상 만나는 모든 점, 마지막으로 끝점을 출력한다. 각 점은 한 줄에 하나씩 x좌표와 y좌표를 공백 하나로 구분해 출력하고, 그 테스트 케이스의 마지막 줄에는 0을 출력한다. 교차점은 적어도 두 도로(표지판이 아닌 선분)가 만나는 점을 말하므로, 표지판이 도로에 닿기만 하는 점은 출력하지 않는다. 시작점에서 끝점으로 가는 경로가 없으면 그 테스트 케이스의 출력으로 -1만 출력한다.