Награда за задачу
100
Рассмотрим координатную плоскость, которую планируется очищать с использованием робота пылесоса. Робот-пылесос представляет собой квадрат размером k ×k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно — в точке (k, k). Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характе- ризуется направлением di , принимающим значения ‘N’ (вверх, увеличение координаты Y ), ‘S’ (вниз, уменьшение координаты Y ), ‘W’ (влево, уменьшение координаты X) или ‘E’ (вправо, увеличение координаты X), и целым числом ai — расстоянием, на которое робот перемещается. di = 'N', ai = 2 d k = 1 i = 'W', ai = 2 di = 'S', ai = 3 di = 'E', ai = 4 -2 (0, 0) -3 4 2 (1, 1) X Y 1 1 3 -1 -1 -2 -3 2 3 5 6 7 8 На рисунке приведены примеры возможных перемещений робота в каждом направлении. Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка счита- ется убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k × k, на котором находился робот. По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.
В первой строке ввода через пробел даны два целых числа: размер робота k и количество команд n (1 6 k 6 104 ; 1 6 n 6 105 ). В i-й из следующих n строк через пробел даны направление i-го перемещения di и его расстояние ai (di — буква ‘N’, ‘S’, ‘W’ или ‘E’; 1 6 ai 6 109 ).
Выведите суммарную площадь убранной роботом поверхности.
Автор задачи: FunRoom
