Solved by 53 users: ...
UserDateAttemptTimeCMSC
Rizvanov`23 jan 2008`C++600.15579
mak_kbtu`21 jun 2009`Java100.98709
fetetriste`20 dec 2009`C++200.21756
ethanhunt`28 may 2011`C++2300.09771
ethanhunt`28 may 2011`C++2200.08772
ethanhunt`28 may 2011`C++2100.08793
ethanhunt`28 may 2011`C++2700.05801
ethanhunt`28 may 2011`C++2600.05805
olzhas_kbtu`10 jul 2009`Java100.93820
Pakita`29 jul 2009`Java501.07826
DAV`25 sep 2008`C++500.09850
murphy`05 sep 2009`C++500.15890
defrager`24 feb 2009`C++200.10899
zmy`27 dec 2007`C++800.10914
 C++ 43 Java 5 Kylix 5 FPC 2
` >  >  >  >  >  >  >  >  >  > `

## Prisoner

Time limit = 2 second(s)

(THIS IS DRAFT)

Prisoner Nickolay Borsov escaped from prison and now he is in the forest. And forest is very dense. One can use only paths going through it.

Paths are equally distanced (1 kilometer) straight line going from the south to the north, and from the west to the east.

Forest is rectangular.

Police wants to catch him and make catching barriers, which are straight segment with endpoints ant paths intersections.

Nickolay should find the way from point A to point B (where his frinds are waining for him with helicopter) not intersecting barriers.

Mafia found you and give you task to program algorithm that finds the shortest path. Price is your life.

Input

```N M K
ax ay bx by
sx1 sy1 fx1 fy2
sx2 sy2 fx2 fy2
....
sxK syK fxK fyK
```

N — is WEST-EAST length, M — is SOUTH-NORTH length. K is the number of barriers.

The firts line contains N, M, and K. The second line contains coordinates of the points A and B.

K lines after the first two lines contain descriptions of barriers.

Coordinates are from [0, N] (x-coordinate) and [0, M] (y-coordinate).

Output Two lines. The first conains shortest path length. The second — description of the path — word consisting of letters N, S, W, E, i.e. instruction describing how Nickolay should go through the forest from A to B.

Output "NO SOLUTION" if there is now path from A to B.

 Input#1```4 5 3 3 1 3 4 2 2 4 3 0 4 1 4 2 4 2 5 ``` Output#1```7 WWNNEEN ```
 Input#2```4 5 3 3 1 3 4 2 2 4 3 0 4 1 4 2 2 2 3 ``` Output#2```NO SOLUTION ```

Author:
Andrey Ulanov, Personal Programming MIPT Contest, 7 October 2007
4 October 2007

 © acm.mipt DevGroupThe page was generated in 200ms