#P2307. Treasure Map

Treasure Map

Description

You have come into possession of a pirate map that gives a series of steps to get from your landing place on a desert isle to the spot marked X where the treasure is located. Each step consists of a compass heading and a number of paces.

After spending most of your savings chartering 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 astonished to learn that the pirates had no knowledge 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 depending 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.

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.

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.

2
NbE 10
EbS 10
90.00
2
NbE 10
EbS 10
-90.00
0
14.14
10.00

Source

Waterloo local 2003.09.20