|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.
Сложность Гамма
Космический корабль "Север-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".
|
Ввод 1
|
Ввод 2
|
2 1
100 100 1.7
800 800 198
|
2 1
100 100 1.7
800 800 199.3
|
|
Вывод 1
|
Вывод 2
|
YES
|
NO
|
Для отправки решений необходимо выполнить вход.
|