Problem 116: Target City
(U.M. ACM Runoffs 2003, problem 3)
Description
The street plan of Target City is very unusual. Two perfectly
straight roads, one going North-South and one going East-West,
meet at the exact centre of the city. There are also 50
perfectly circular roads, each centred on that intersection,
with radii of 1, 2, 3, 4, ..., 50 miles (it is a very big city).
Those are the only roads in the city. You can see a map
(showing only an area up to 5½ miles from the city centre)
below.
Homes may be built anywhere on any of the circular roads. The
map shows the locations of four homes, labelled a, b, c, and d.
Addresses within Target City are simply two integers, the first
being the direction from the city centre to the home in question
(in degrees, 0=North, 90=East, 180=South, 270=West, etc), and the
second being the distance from the centre of the city (i.e.
the number of the circular road that it is on). Referring to
the map above:
The
address of home "a" is 0 4.
The
address of home "b" is 40 4.
The
address of home "c" is 75 5.
The
address of home "d" is 200 3.
Your job is to write a program that works out how far a Targettian
will have to drive to get from one address to another. Drivers
must keep to roads at all times, but may take any road in any direction,
and may make any turns desired. Of course, there is always
more than one way to get between any two addresses, you must
find the shortest. For example, to get from a to b, the shortest
route is obviously to drive straight alongcircular road 4, for
a total of 40°, which results in a distance of 2.79 miles.
To get from a to d, the fastest route is to drive straight down
the North-South road for seven miles, then turn onto circular
road 3 for the remaining 20°, giving a total distance of
8.047 miles.
Input Format
The input will consist of a number of queries. Each query
consists of four integers on a line separated by spaces. The four integers,
a1, r1, a2, r2, are the addresses (a1, r1) and (a2, r2)
of the two homes. A1 and a2 will be between 0 and 359
inclusive, and r1 and r2 will be between 0 and 50 inclusive.
After the last line of input, the file will end; there
will be no special symbol in the file.
Output Format
For each input case, there must be exactly one line of output.
That line should show the shortest distance between the two
addresses, in miles, rounded to two places after the decimal point.
Limits
Addresses range from 0 1 to 359 50.
Sample Input
0 4 40 4
0 4 200 3
5 10 85 11
5 10 75 11
270 5 90 5
Sample Output
2.79
8.05
16.80
16.27
10.00
End of Problem