АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

175. Марсоход

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Космический корабль "Север-2006" успешно достиг Марса, спуск марсохода тоже прошёл в штатном режиме. Хотя марсоход и рассчитан на передвижение по неровной поверхности, его не стоит подвергать лишней опасности. Лучше всего, если марсоход сможет попасть из начальной точки в конечную, избегая кратеры. "Север-2006" сделал снимок местности из космоса. Ваша задача — написать программу, которая по снимку местности, начальным и конечным координатам марсохода определит, существует ли безопасный путь из одной точки в другую.

Формализуем задачу.

Снимок местности представляет собой квадрат, левый нижний угол которого имеет координаты (0, 0), а правый верхний (1000, 1000). Марсоход будем считать кругом радиуса R. На снимке различимы N кратеров в форме кругов. Центр k-го кратера имеет координаты (xk, yk), радиус k-го кратера равен rk. Изначально марсоход находится в левом нижнем углу карты, т.е. его центр имеет координаты (R, R). Попасть марсоход должен в правый верхний угол карты, т.е. в точку с координатами
(1000 – R, 1000 – R). Чтобы маршрут был безопасным, марсоход не должен выходить на неизвестную территорию (за края карты), но может касаться края карты. Также марсоход не должен заезжать на кратер, но может его касаться. Кратеры могут пересекаться и даже один находиться внутри другого, в последнем случае внутренний кратер можно игнорировать.

Первая строка входного файла содержит два целых числа N и R (0 <= NR <= 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

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / IX Межвузовская олимпиада 2006 /
174. D - Выполнимость 175. 176. F - Сообщение 177. G - Скобки 178. H - Транслятор
 
время генерации 0.063 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.