Walls ----- The Grand Mazzz of Zurrr has the prettiest walls. Some are made of colored glass, some of rubies, some of silver, and even one of gold. Every morning Fritzzz must run through the Mazzz to wait on the King of Zurrr. This is annoying and time consum- ing, not to mention that if Fritzzz gets lost he might never get out! Fortunately Fritzzz has a map of the Mazzz, although it is so big its hard to use it to plan a strategy. But he has encoded the map as computer data and hopes you can help him find the shortest path through the Mazzz. Input ----- For each test case, first a line that gives the test case name. Then a line of the form X Y N giving the X and Y dimensions of the Mazzz and the num- ber of walls N. Then there are N lines each containing X1 Y1 X2 Y2 defining a wall whose ends are at (X1,Y1) and (X2,Y2). All walls are straight. Two or more walls may have a common endpoint, but otherwise walls do not intersect or overlap. Two walls that have a common endpoint may be parallel. All walls are of non-zero length. Four of the walls bound the Mazzz, and are called boundary walls. No other walls have endpoints on the Mazzz boundary. All input numbers are integers. 4 <= N <= 500 100 <= X,Y <= 10,000 0 <= X1, X2 <= X 0 <= Y1, Y2 <= Y Fritzzz starts at (0,0) and has to get to (X,Y). Input ends with an end of file. Test case name lines are at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then a line containing just L which is the shortest distance that Fritzzz must travel to get from (0,0) to (X,Y) while staying inside the Mazzz. L must be accurate to 2 decimal places. Fritzzz can go arbitrarily close to walls. If walls join at a common endpoint, or corner, Fritzzz can go around the corner but not through it. Since only boundary walls touch the boundary, Fritzzz could run along the boundary, so necessarily L < X+Y. Sample Input ------ ----- -- SAMPLE 1 -- 100 100 24 0 0 0 100 0 100 100 100 100 100 100 0 100 0 0 0 30 30 40 40 25 25 30 5 50 50 60 60 20 40 30 30 60 60 70 70 70 70 80 80 50 30 60 60 89 10 60 60 5 20 10 15 10 15 15 20 20 10 10 5 85 85 90 90 75 95 90 90 90 80 90 90 10 10 20 20 10 10 20 10 20 20 15 20 20 40 20 80 5 20 10 80 30 5 50 10 Sample Output ------ ------ -- SAMPLE 1 -- 148.31 Display ------- The command display_walls -X walls.in can be used to display test case input. See display_walls -doc for more documentation. File: walls.txt Author: Bob Walton Date: Sun Sep 23 12:09:24 EDT 2018 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.