eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Марсоход

Марсоход

Космический корабль "Север-2006" успешно достиг Марса, спуск марсохода тоже прошёл в штатном режиме. Хотя марсоход и рассчитан на передвижение по неровной поверхности, его не стоит подвергать лишней опасности. Лучше всего, если марсоход сможет попасть из начальной точки в конечную, избегая кратеры. "Север-2006" сделал снимок местности из космоса. Ваша задача - написать программу, которая по снимку местности, начальным и конечным координатам марсохода определит, существует ли безопасный путь из одной точки в другую. Формализуем задачу. Снимок местности представляет собой квадрат, левый нижний угол которого имеет координаты (\textbf{0}, \textbf{0}), а правый верхний (\textbf{1000}, \textbf{1000}). Марсоход будем считать кругом радиуса \textbf{r}. На снимке различимы \textbf{N} кратеров в форме кругов. Центр \textbf{k}-го кратера имеет координаты (\textbf{x_k}, \textbf{y_k}), радиус \textbf{k}-го кратера равен \textbf{r_k}. Изначально марсоход находится в левом нижнем углу карты, т.е. его центр имеет координаты (\textbf{r}, \textbf{r}). Попасть марсоход должен в правый верхний угол карты, т.е. в точку с координатами (\textbf{1000-r}, \textbf{1000-r}). Чтобы маршрут был безопасным, марсоход не должен выходить на неизвестную территорию (за края карты), но может касаться края карты. Также марсоход не должен заезжать на кратер, но может его касаться. Кратеры могут пересекаться и даже один находиться внутри другого, в последнем случае внутренний кратер можно игнорировать. \InputFile Первая строка ввода содержит два целых числа \textbf{n} и \textbf{r} (\textbf{0} ≤ \textbf{n}, \textbf{r} ≤ \textbf{100}). Следующие \textbf{n} строк содержат описания кратеров, \textbf{k}-тый кратер задаётся тремя действительными числами \textbf{x_k}, \textbf{y_k}, \textbf{r_k}, находящимися в одной строке и разделёнными пробелом (\textbf{0} ≤ \textbf{x_k}, \textbf{y_k}, \textbf{r_k} ≤ \textbf{1000}). Все действительные числа содержат от \textbf{0} до \textbf{5} цифр после десятичной точки. \OutputFile Выведите слово \textbf{YES} (большими буквами, без кавычек), если существует безопасный путь марсохода, в противном случае выведите слово \textbf{NO}.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
2 1
100 100 1.7
800 800 198
Выходные данные #1
YES
Автор Павел Кузнецов