Космический
корабль "Север-2006" успешно достиг Марса, спуск марсохода тоже
прошёл в штатном режиме. Хотя марсоход и рассчитан на передвижение по неровной
поверхности, его не стоит подвергать лишней опасности. Лучше всего, если
марсоход сможет попасть из начальной точки в конечную, избегая кратеры.
"Север-2006" сделал снимок местности из космоса. Ваша задача —
написать программу, которая по снимку местности, начальным и конечным
координатам марсохода определит, существует ли безопасный путь из одной точки в
другую.
Формализуем задачу.
Снимок местности представляет
собой квадрат, левый нижний угол которого имеет координаты (0, 0), а правый
верхний (1000, 1000). Марсоход будем считать кругом радиуса R. На снимке
различимы N кратеров в форме кругов. Центр k-го кратера имеет
координаты (xk, yk), радиус k-го
кратера равен rk. Изначально марсоход находится в левом
нижнем углу карты, т.е. его центр имеет координаты (R, R).
Попасть марсоход должен в правый верхний угол карты, т.е. в точку с
координатами
(1000 – R, 1000 – R). Чтобы маршрут был безопасным, марсоход
не должен выходить на неизвестную территорию (за края карты), но может касаться
края карты. Также марсоход не должен заезжать на кратер, но может его касаться.
Кратеры могут пересекаться и даже один находиться внутри другого, в последнем
случае внутренний кратер можно игнорировать.
Первая строка входного
файла
содержит два целых числа N и R (0 <= N, R <= 100). Следующие N строк
содержат описания кратеров. k-тый кратер задаётся тремя действительными
числами xk yk rk,
находящимися в одной строке и разделёнными пробелом (0 < xk,
yk, rk < 1000). Все действительные числа
содержат от 0 до 5 цифр после десятичной точки.
В выходной файл выведите слово "YES" (большими буквами, без
кавычек), если существует безопасный путь марсохода, в противном случае
выведите слово "NO".
Примеры
|
STDIN
|
STDOUT
|
2 1
100 100 1.7
800 800 198
|
YES
|
2 1
100 100 1.7
800 800 199.3
|
NO
|
