WWAKER - The Wind Waker

The world is in danger once again, and Link is the hero who will save us! In order to save the world, Link must travel overseas and collect some legendary items.

The sea can be described as an infinite 2D plane with a Cartesian coordinate system, in which the point (0,0) denotes the center of the sea. Also, the cardinal directions are defined as usual:

Cardinal drections


Link must use his boat to travel. Unfortunately, Link's boat has a limitation: the boat can only move in the same direction as the Wind. So, for instance, if the wind is blowing North, Link can only travel to the North. If the wind is not blowing at all, Link doesn't move at all, too.

Fortunately, Link has the wind waker, the magical baton. With this baton, Link can conduct the Wind's Requiem, a mystical melody that allows Link to control the wind. Each time the wind waker is used, Link can either make the wind stop blowing (this action is represented by the letter X) or make the wind blow in one of the 8 cardinal directions (North (N), South (S), East (E), West (W), Northeast (NE), Southeast (SE), Southwest (SW), Northwest(NW)).

Wind Waker

Link using the wind waker


Link must go to the position (x2,y2) and stop there, to collect a legendary item. Right now, Link is at the position (x1,y1) and the wind is not blowing. You must find a trajectory from (x1,y1) to (x2,y2). A trajectory consists of a sequence of uses of the wind waker at certain positions. For example, to go from (0,0) to (1,1), a possible trajectory is:

  1. At point (0,0), make the wind blow north;
  2. At point (0,1), make the wind blow east;
  3. At point (1,1), make the wind stop blowing.

You must find a trajectory that:

  • Minimizes the number of times Link uses the wind waker;
  • In case of a tie, minimizes the total distance traveled;
  • In case of a tie, uses the lexicographically smaller sequence of wind direction changes. Use E < N < NE < NW < S < SE < SW < W < X. For example, a trajectory that changes the wind to N, then to SW, then to W is preferable over a trajectory that changes the wind to N, then to W, then to E, because (N,NW,W) is lexicographically smaller than (N,W,E) (because N=N, NW < W).


Check the sample input and output.

Note: The names "Link", "The Wind Waker" and some images above are copyrighted by Nintendo (r).
The author just wanted to make the problem more interesting. The author supports Nintendo!

Input

The input file consists of one or more test cases. Each test case is described by a line containing four integers x1, y1, x2, y2 (|x1|, |y1|, |x2|, |y2| ≤ 5 × 104, (x1, y1) (x2, y2)).

The file ends with EOF.

Output

For each test case, print a line containing K, the number of times the wind waker is used. In the next K lines print xi yi D, meaning that the wind waker must be used to change the wind direction to D at the position (xi,yi). Print the coordinates rounded to exactly two fractional digits, and use D='S',N','W','E','SE','SW','NE','NW' or 'X'. Print the events in the order they occur in the trajectory.

After the K lines, print the total distance traveled, rounded to exactly three fractional digits. Print a blank line after each test case. Check the sample output.

Example

Input:
0 0 0 1
0 0 3 2 Output:
2
0.00 0.00 N
0.00 1.00 X
1.000

3
0.00 0.00 E
1.00 0.00 NE
3.00 2.00 X
3.828


Added by:Ricardo Oliveira [UFPR]
Date:2013-03-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2013-10-31 03:04:07 Martijn Muijsers
Slowest solution, but that may well be because of the crazy amount of stuff I put around some things to make them work. First I did some linear algebra but then I realized I had to type out solutions anyway XD I guess the trick to solving is is trying lots of cases. Great problem!!
2013-08-26 15:15:04 Miguel Oliveira
quite tricky. had to make a brute force to clear the bugs
2013-03-15 12:56:43 Ricardo Oliveira [UFPR]
Yes. "Each test case is described by a line containing four integers ..."
2013-03-15 12:56:43 Archit Mittal
are x1,y1,x2,y2 int only

Last edit: 2013-03-13 16:02:03
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.