Задача №1143. Стена
Чтобы защитить свою страну от набегов кочевников, президент Флатландии решил построить Великую Флатландскую Стену. Страна Флатландия представляет собой координатную плоскость, ее столица находится в точке (0, 0). Именно из столицы и планируется начать строительство стены. Министру внутренних дел срочно поручили составить план постройки стены.
План постройки стены представляет собой последовательность инструкций строителям. Инструкции бывают следующего вида:
<направление строительства> <длина>
<направление перемещения> <расстояние>
В первом случае строители возводят стену указанной длины от точки, где они находятся, в указанном направлении. Во втором случае строители перемещаются на указанное расстояние в указанном направлении, не возводя при этом стены
Направление строительства задается заглавной латинской буквой, а направление перемещения – строчной латинской буквой. Соответствие букв направлениям приведено в следующей таблице:
-
Буква
Направление
Вектор
N n
Север
(0, 1)
E e
Восток
(1, 0)
S s
Юг
(0, -1)
W w
Запад
(-1, 0)
Длина и перемещение задаются в километрах и представляют собой целые числа.
Однако оказалось, что план министра может оказаться невыполнимым – в некоторый момент строители при выполнении инструкции могут столкнуться с уже построенной ими стеной! Выясните, выполним ли план министра и если нет, выведите координаты точки, в которой впервые произойдет столкновение с уже построенной стеной.
На первой строке входного файла расположено число N – количество инструкций в плане министра (0 N 1000). Последующие N строк содержат инструкции плана. Их формат следующий: сначала идет одна из допустимых букв, заглавная буква означает, что следует строить стену, а строчная – что следует просто переместиться. Затем, отделенное от буквы ровно одним пробелом, идет целое число Xi - какой длины следует строить стену, либо на сколько надо переместиться (1 Xi 106).
На первой строке выходного файла выведите yes, если план можно выполнить, либо no, если нельзя. План можно выполнить, если строители, которых будем считать материальной точкой, никогда не оказываются в точке, через которую проходит участок стены, отличный от того, который они сейчас строят или только что построили (считаем стену состоящей из отрезков). В случае отрицательного ответа выведите на второй строке координаты точки, в которой произойдет столкновение со стеной, сначала X, затем Y. Числа должны быть разделены пробелом.
4 n 10 e 10 s 10 w 10
YES
4 n 10 e 10 s 10 W 10
YES