print2102. Волшебный ящик

printВолшебный ящик

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Владислав очень любит различные шоу иллюзионистов. После просмотра очередного шоу его очень заинтересовал номер, в котором в ящик залезала помощница иллюзиониста и он протыкал этот ящик множеством шпаг, после чего девушка живая и невредимая вылезала обратно.
Владислав решил дома попробовать повторить этот фокус. В качестве ящика он взял прямоугольный параллелепипед размером `L`x`D`x`D`. Поскольку Владиславу не хотелось подвергать опасности человеческую жизнь, он решил поместить в ящик свой любимый футбольный мяч, который имеет форму шара с диаметром ровно `D`.
Помимо этого, юный фокусник разметил на сторонах параллелепипеда, имеющих размер `D`x`L`, несколько точек, в которых он будет протыкать ящик шпагами насквозь. Грани квадратной формы (размером `D`x`D`) он решил не протыкать.
Во время выполнения фокуса Владиславу все не удавалось разместить мяч так, чтобы не было опасности проткнуть его одной из шпаг. Поскольку Владислав очень дорожит своим мячом, он просит вас выяснить, существует ли такое расположение мяча в ящике, при котором ни одна шпага не проткнет его (при этом, возможно, будет касаться его). Каждая шпага при этом считается пренебрежимо тонкой.
Первая строка входного файла содержит три целых числа: `N`, `D` и `L` (`0\ ≤\ N\ ≤\ 100000`, `1\ ≤\ D,\ L\ ≤\ 10^9`) – количество шпаг и размеры ящика и мяча.
Следующие `N` строк содержат описания точек, в которых ящик будет проткнут шпагами.
Для удобства описания этих мест, Владислав расположил ящик так, что прямо перед ним расположена одна из сторон, размером `D`x`L`, которую он назвал передней и ввел на ней прямоугольную систему координат с центром в левом нижнем углу. Правый верхний угол при этом имеет координату `(L,\ D)`. Аналогичную систему координат он ввел на верхней грани, которая также имеет размер `D`x`L`, при этом смотрел на нее он сверху. Поскольку Владислав не протыкает ящик шпагами со стороны квадратной грани (размером `D`x`D`), то этих систем координат ему хватило для обозначения всех точек протыкания.
Строка вида F `x\ y` (`0\ ≤\ x\ ≤\ L`, `0\ ≤\ y\ ≤\ D`) описавает протыкание передней грани в точке с координатами `(x,\ y)`. А строка вида U `x\ y` (`0\ ≤\ x\ ≤\ L`, `0\ ≤\ y\ ≤\ D`) описавает протыкание верхней грани в точке с координатами `(x,\ y)`. Все координаты целые. Все точки различны.
В выходной файл выведите YES, если возможно так расположить мяч в ящике, чтобы он не был проткнут ни одной шпагой, или NO в противном случае.

Пример ввода 1

2 2 4
U 1 1
F 3 1

Пример вывода 1

YES

Пример ввода 2

2 2 3
U 1 1
F 2 1

Пример вывода 2

NO
Источник: neerc.ifmo.ru/school
loading