SPOJ Brasil

O mundo está em perigo mais uma vez, e Link é o herói que irá nos salvar! Para nos salvar, Link precisa navegar pelos mares e obter alguns itens lendários.

O mar pode ser descrito como um plano 2D infinito com um sistema de coordenadas Cartesianas, no qual o ponto (0,0) denota o centro do mar. As direções cardeais são definidas de maneira usual:

Link deve usar seu barco para navegar. O barco de Link, entretanto, tem uma limitação: ele se move apenas na direção do vento. Assim, por exemplo, se o vento está soprando para o norte, Link pode viajar apenas para o norte. Além disso, se o vento não está soprando, Link não se movimenta.

Felizmente, Link tem o wind waker, a batuta mágica. Com esta batuta, Link pode conduzir o Wind's Requiem, uma melodia mística que permite controlar o vento. Cada vez que o wind waker é utilizado, Link pode fazer o vento parar de soprar (ação representada pela letra X) ou fazer o vento soprar em uma das 8 direções cardeais (norte (N), sul (S), leste (E), oeste (W), nordeste (NE), sudeste (SE), sudoeste (SW), noroeste (NW)).

Link usando o wind waker

Link deve ir para a localização (x₂,y₂) e parar para colecionar um item. Neste momento, Link está na localização (x₁,y₁) e o vento não está soprando. Você deve encontrar uma trajetória de (x₁,y₁) para (x₂,y₂). Uma trajetória consiste em uma sequência de usos do wind waker em localizações específicas. Por exemplo, para ir de (0,0) até (1,1), uma possível trajetória é:

1. Em (0,0), faça o vento soprar para o norte;
2. Em (0,1), faça o vento soprar pra o leste;
3. Em (1,1), faça o vento parar de soprar.

Você deve encontrar uma trajetória que:

• Minimiza o número de vezes que Link usa o wind waker;
• Em caso de empate, minimiza a distância total percorrida;
• Em caso de empate, usa a lexicograficamente menor sequência de mudanças de direção do vento. Considere E < N < NE < NW < S < SE < SW < W < X. Por exemplo, uma trajetória que muda a direção do vento para N, para SW, e para W é preferível sobre uma trajetória cujas mudanças são N, W e E, pois (N,NW,W) é lexicograficamente menor que (N,W,E) (pois N=N e NW < W)

Verifique os exemplos de entrada e saída.

Entrada

O arquivo de entrada contém vários casos de teste. Cada caso de teste é descrito por uma linha contendo quatro inteiros x₁, y₁, x₂, y₂ (|x₁|, |y₁|, |x₂|, |y₂| ≤ 5 × 10⁴, (x₁, y₁) _≠ (x₂, y₂)).

A entrada termina com fim-de-arquivo (EOF).

Saída

Para cada caso de teste, imprima uma linha contendo K, o número de vezes que o wind waker é utilizado. Nas próximas K linhas, imprima  x_i y_i D, indicando que o wind waker deve ser utilizado para trocar a direção do vento para D na posição (x_i,y_i). Imprima as coordenadas arredondadas com duas casas decimais, e use D='S',N','W','E','SE','SW','NE','NW' ou 'X'. Imprima os eventos na ordem em que ocorrem na trajetória.

Após as K linhas, imprima a distância total viajada, arredondada com três casas decimais. Imprima uma linha em branco após cada caso de teste. Verifique o exemplo de saída.

Exemplo

Entrada:
0 0 0 1
0 0 3 2

Saída:
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