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.