Tri-Mare -------- You live and work in the city of Tri-Mare, which is built in a shallow section of the sea (like Venice) so that people travel around it in boats. You want to find the shortest path from your apartment to work. All the buildings in Tri-Mare are triangular prism high-rises with elevators at their corners. You go down one of the elevators from your apartment and drive your own boat to a corner of the building you work in and take the elevator up to your office. You want to find the shortest path for the boat (ignor- ing your paths inside buildings). The boat can travel alongside a building, but not through a building. Input ----- For each test case, first a line that gives the test case name. Then a line of the form N giving the number of buildings in Tri-Mare, and then N lines, one per building, of the form X1 Y1 X2 Y2 X3 Y3 giving the 3 corners of the building, which are (X1,Y1), (X2,Y2), and (X3,Y3). All numbers are integers. The buildings are numbered 1, 2, ..., N in the order of their description lines. You live in building 1 and work in building N. 2 <= N <= 100 -1,000,000 <= Xi,Yi <= +1,000,000 Input terminates with an end of file. The test case name line is at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then a line containing just the length of the shortest path from any corner of building 1 to any corner of building N. The length must be accurate to one part in 10**5 (use default floating point format which prints 6 digits of precision). Sample Input ------ ----- -- SAMPLE 1 -- 2 0 0 10 10 0 10 30 40 50 80 40 100 -- SAMPLE 2 -- 3 0 0 10 10 0 10 15 25 35 15 25 55 30 40 50 80 40 100 Sample Output ------ ------ -- SAMPLE 1 -- 36.0555 -- SAMPLE 2 -- 50.9902 File: trimare.txt Author: Bob Walton Date: Sat Oct 7 14:12:00 EDT 2017 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.