Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Geometric Map
Description Your task in this problem is to create a program that finds the shortest path between two given locations on a given street map, which is represented as a collection of line segments on a plane. Figure 4: An example map Figure 4 is an example of a street map, where some line segments represent streets and the others are signs indicating the directions in which cars cannot move. More concretely, The sign You should write a program that finds the shortest path obeying these traffic rules. The length of a line segment between ( Input The input consists of multiple datasets, each in the following format.
y_{s}x _{g}y_{g}x_{1}^{1} y_{1}^{1} x_{2}^{1} y_{2}^{1}⋮ x_{1}^{k} y_{1}^{k} x_{2}^{k} y_{2}^{k}⋮ x_{1}^{n} y_{1}^{n} x_{2}^{n} y_{2}^{n}
( y) and (_{s}x, _{g}y) are the start and goal points, respectively. You can assume that (_{g}x, _{s}y) ≠ (_{s}x, _{g}y) and that each of them is located on an end point of some line segment representing a street. You can also assume that the shortest path from (_{g}x, _{s}y) to (_{s}x, _{g}y) is unique._{g}( All the coordinates are non-negative integers less than or equal to 1000. The end of the input is indicated by a line containing a single zero. Output For each input dataset, print every Print −1 if there are no paths from the start point to the goal point. Sample Input 8 1 1 4 4 1 1 4 1 1 1 1 4 3 1 3 4 4 3 5 3 2 4 3 5 4 1 4 4 3 3 2 2 1 4 4 4 9 1 5 5 1 5 4 5 1 1 5 1 1 1 5 5 1 2 3 2 4 5 4 1 5 3 2 2 1 4 2 4 1 1 1 5 1 5 3 4 3 11 5 5 1 0 3 1 5 1 4 3 4 2 3 1 5 5 2 3 2 2 1 0 1 2 1 2 3 4 3 4 5 5 1 0 5 2 4 0 4 1 5 5 5 1 2 3 2 4 0 Sample Output 1 1 3 1 3 4 4 4 0 -1 5 5 5 2 3 1 1 0 0 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator