An 8-point compass rose, commons.wikimedia.org
"Ahoy mateys! Arrr... We pirates look for sunken treasure. Which direction we sail?"
"Shiver me timbers!" The pirate captain is a superstitious sea-dog and only likes to sail in the exact directions of an 8-point compass rose: north (N), south (S), east (E), west (W), north-east (NE), south-east (SE), north-west (NW) and south-west (SW).
"Arrr!" So you scallywags need to come up with a list of directions for the captain to follow, in order to go from one $$$(x,y)$$$ point in the sea to another $$$(x,y)$$$ point while traversing the least possible distance. Only the directions are necessary; the captain is no landlubber and will figure out how long to go in each direction. The captain sails a positive distance in every direction you list.
For example, if the ship is at (2,1) and the treasure is at (6,8), we can tell the captain to first sail N to (2,4) then NE to the treasure traversing the least possible distance. It would be possible to arrive by first going E to (6,1) then N: but this is not a shortest path.
Illustration for sample 1. N then NE is a shortest path. E then N is not.
The input consists of:
- One line with two integers $$$x_s$$$ and $$$y_s$$$ ($$$-5400 \leq x_s,y_s \leq 5400$$$), the starting position of the ship.
- One line with two integers $$$x_t$$$ and $$$y_t$$$ ($$$-5400 \leq x_t,y_t \leq 5400$$$), the position of sunken treasure.
Output the directions that the captain should follow to reach the sunken treasure while traversing the least possible distance. Each direction should be one of: "N", "S", "E", "W", "NE", "SE", "SW", "NW".
If there are multiple valid solutions, you may output any one of them.
2 16 8
N NE
0 00 -60
S
2 1-2 -1
SW W W SW
