Treasure Map

You have come into possession of a pirate map that gives a series of steps to get from your land- ing place on a desert isle to the spot marked X where the treasure is located. Each step con- sists of a compass heading and a number of paces. After spending most of your savings charter- ing a boat, you arrive at the island and, with the help of your portable GPS receiver, duly execute the instructions on the map. Alas, no treasure! On your return home you are aston- ished to learn that the pirates had no knowl- edge of GPS and used a magnetic compass to create the map. The pirates were unaware that their compass pointed to magnetic north rather than true north. The relative angle between magnetic north and true north varies depend- ing where you are on the planet, but you are able to determine that on this particular desert isle, magnetic north is d degrees from true north. How close were you to the spot marked X at any moment while following the map? Input There are several test cases. Each test case begins with n ≤ 1000, the number of steps in the map. n lines follow; each consists of one of the 32 named compass points shown at right followed by a number of paces. The last line is a number giving the angle between magnetic north and true north, in degrees. A positive number indicates that magnetic north is to the east of true north; a negative indicates that it is to the west. The magnitude of this angle will not exceed 90 degrees. A line containing ‘0’ follows the input for the last case. Output For each test case, output a single number, rounded to two decimal places, giving the least distance (in paces) that separated you from the treasure at any point while you were following the map. Note: We use combinations of the letters N, E, S, W, b to abbreviate the names of the compass points. For example, ‘NEbE’ stands for north-east by east. The 32 points are equally spaced about the compass. Clockwise, they are: N, NbE, NNE, NEbN, NE, NEbE, ENE, EbN, E, EbS, ESE, SEbE, SE, SEbS, SSE, SbE, S, SbW, SSW, SWbS, SW, SWbW, WSW, WbS, W, WbN, WNW, NWbW, NW, NWbN, NNW, NbW. Sample Input 2 NbE 10 EbS 10 90.00

2/2 2 NbE 10 EbS 10 -90.00 0 Sample Output 14.14 10.00