Geometric Map#5830
Your task in this problem is to write a program that finds the shortest path between two given points on a street map represented by a set of line segments in the plane.
Figure 1: Example of a street map
In Figure 1, some line segments represent streets, while others are signs indicating directions in which vehicles are prohibited from moving. Specifically, AE, AM, MQ, EQ, CP, and HJ represent the streets; the others are signs. In general, one end point of a sign touches exactly one line segment representing a street, and the other end is open. Each endpoint of a street will touch one or more streets, but not any signs.
The sign BF, for example, indicates that at point B, vehicles can move from left to right but not in the reverse direction. In general, vehicles may not move from the obtuse-angle side to the acute-angle side at a point where a sign touches a street (e.g., angle CBF is obtuse, while angle ABF is acute). Vehicles cannot move directly from P to M nor from M to P, since vehicles going left to right cannot go through N, and those going right to left cannot go through O. In the special case where the angle between a sign and a street is a right angle, vehicles cannot move in either direction at the point. For instance, vehicles cannot move directly from H to J or from J to H.
You must write a program that finds the shortest path obeying these traffic rules. The length of a segment between (x_1, y_1) and (x_2, y_2) is the usual Euclidean distance.
The input consists of multiple datasets, each in the following format:
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
is the number of line segments, a positive integer not exceeding .
(x_s, y_s) and (x_g, y_g) are the start and goal points, respectively. You may assume (x_s, y_s) \neq (x_g, y_g), and each of them is located at an endpoint of some street segment. You may also assume that the shortest path from (x_s, y_s) to (x_g, y_g) is unique.
(x^k_1, y^k_1) and (x^k_2, y^k_2) are the two endpoints of the -th line segment. You may assume (x^k_1, y^k_1) \neq (x^k_2, y^k_2). No two segments cross or overlap except possibly at endpoints; that is, if two segments share a point, it is always one of their endpoints.
All coordinates are non-negative integers not exceeding . The end of the input is indicated by a line containing a single zero.
For each input dataset, print each street intersection point on the shortest path from the start to the goal, one per line in that order, followed by a line containing a single zero. A street intersection point is a point where at least two street segments meet. Each output line for a street intersection point should contain its - and -coordinates separated by a space.
Print if there is no path from the start point to the goal point.
Example 1