- Описание
- Отправленные решения
464. Оставаясь на связи
Альпинист Тимофей решил отправиться в долгий поход по горам Алтая. Тимофей знает, насколько важно иметь доступ к связи во время путешествия, и поэтому изучает карту вышек сотовой связи своего оператора, чтобы убедиться в наличии мобильной связи на своём маршруте. В последнее время Тимофею некогда анализировать данные вручную, и он решил написать программу, которая определит доступность связи на нужной Тимофею местности.
Будучи опытным программистом, Тимофей воспринимает карту местности как прямоугольную сетку. Для каждой вышки сотовой связи он выяснил её местоположение и радиус действия. Считается, что в точке на карте есть сотовая связь, если точка находится в радиусе действия хотя бы одной вышки сотовой связи. Современные вышки настолько продвинутые, что их радиус действия охватывает квадрат, а не круг:
Пример области действия вышки с радиусом, равным 2
Тимофей тоже продвинутый и умеет перемещаться из любой точки прямоугольной сетки не только по вертикали и горизонтали, но и по диагонали. Требуется понять, существует ли между двумя точками на карте такой маршрут, который подходит под требования Тимофея.
Формат ввода
В первой строке входных данных находится количество вышек сотовой связи .
В следующих строках находятся данные сотовой вышки , где , — координаты вышки, — радиус её действия и ().
В следующей строке передаются координаты — старт маршрута.
В следующей строке передаются координаты — конец маршрута.
Формат вывода
1 — если можно проложить маршрут, удовлетворяющий требованиям Тимофея.
0 — если такого маршрута не существует.
Ограничения
Ограничение времени
3 с
Ограничение памяти
128 МБ
Пример 1
3
1 1 1
4 4 2
7 1 1
0 0
8 0
1
Пример 2
3
1 1 1
4 4 2
7 1 1
0 0
1 7
0