Whoosh ------ Every ten years the city of Whoosh has a solo-pedal race from one end of the city to the other. Whoosh is known as a city that is just one big paved flat area in which solo-pedallers go whooshing around. But the race is made interesting because the buildings are in the way; solo-pedallers may not go into a building. You have been asked by a friend who is participating to find a shortest path around the buildings. Whoosh is laid out as a North-South East-West grid of squares, each square containing exactly one building. The corners of the squares are race waypoints, and by rule your route must go from waypoint to waypoint. In addition, any two consecutive waypoints on your route must be corners of the SAME square. If you go straight North, South, East, or West from a waypoint you will not go through a building. But if you go diagonally across a square, you may or may not have to go around the side of the building in the square. If you need to go around, your route may hug the side of the building. The buildings in Whoosh are all ellipses, so solo- pedallers cannot injure themselves by running into sharp corners. You have a map of Whoosh showing the buildings, so it should be simple. WARNING: The sine an cosine functions take too long to be executed millions of times per test case, so they must be used sparingly. Input ----- A sequence of test cases. Each test case begins with a line containing the test case name. The next line contains M N L specifying that the Whoosh grid has M rows of N squares each, and the square sides are each L feet long. The waypoint xy-coordinates range from (0,0) in the lower left to (L*M,L*N) in the upper right. The races starts at (0,0) and ends at (L*M,L*N). Then there are M*N lines each specifying one building. Each of these lines has the form: cx cy angle minor major and describes a building whose footprint is an ellipse with center (cx,cy), given angle of major axis, and given lengths in feet of minor and major semi-axes. The angle is measured in degrees counter-clockwise from the positive x-axis in the usual way. A semi-axis is one half an axis, so if angle == 0 the equation of the ellipse would be: ((x-cx)/major)^2 + ((y-cy)/minor)^2 = 1 There is exactly one building for each grid square, but the building description lines are in arbitrary order. All input numbers are integers. 1 <= M,N <= 20 1,000 <= L <= 10,000 0 <= cy <= M*L 0 <= cx <= N*L - 180 < angle <= + 180 50 <= minor <= major <= L/2 - 50 No building part is within 50 feet of a North-South or East-West line running through any waypoint. Input ends 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 just one line giving the length of the shortest route that obeys the rules. The length should be accurate to 1 part in 10^5. Assume the size of a solo-pedal is negligible so if the route includes part of a building perimeter, only the exact length of that perimeter part counts as part of the length. Sample Input ------ ----- -- SAMPLE 1 -- 2 2 1000 600 400 0 100 100 1500 500 0 100 100 500 1500 0 100 100 1500 1500 0 225 225 -- SAMPLE 2 -- 2 3 1000 500 500 0 100 150 1500 500 0 150 200 2500 500 45 75 200 500 1510 30 100 150 1510 1500 60 150 200 2510 1510 120 75 200 Sample Output ------ ------ -- SAMPLE 1 -- 2900.64 -- SAMPLE 2 -- 3882.51 File: whoosh.txt Author: Bob Walton Date: Tue Oct 15 14:09:19 EDT 2019 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.