464. Оставаясь на связи

Не решаласьСредняя

Альпинист Тимофей решил отправиться в долгий поход по горам Алтая. Тимофей знает, насколько важно иметь доступ к связи во время путешествия, и поэтому изучает карту вышек сотовой связи своего оператора, чтобы убедиться в наличии мобильной связи на своём маршруте. В последнее время Тимофею некогда анализировать данные вручную, и он решил написать программу, которая определит доступность связи на нужной Тимофею местности.

Будучи опытным программистом, Тимофей воспринимает карту местности как прямоугольную сетку. Для каждой вышки сотовой связи он выяснил её местоположение и радиус действия. Считается, что в точке на карте есть сотовая связь, если точка находится в радиусе действия хотя бы одной вышки сотовой связи. Современные вышки настолько продвинутые, что их радиус действия охватывает квадрат, а не круг:

<Picture>

Пример области действия вышки с радиусом, равным 2

Тимофей тоже продвинутый и умеет перемещаться из любой точки прямоугольной сетки не только по вертикали и горизонтали, но и по диагонали. Требуется понять, существует ли между двумя точками на карте такой маршрут, который подходит под требования Тимофея.

Формат ввода

В первой строке входных данных находится количество вышек сотовой связи NN.

В следующих NN строках находятся данные сотовой вышки XiX_i YiY_i RiR_i, где XiX_i, YiY_i — координаты вышки, RiR_i — радиус её действия и (0N,Xi,Yi,Ri10000 \le N, X_i, Y_i, R_i \le 1000).

В следующей строке передаются координаты XsX_s YsY_s — старт маршрута.

В следующей строке передаются координаты XfX_f YfY_f — конец маршрута.

Формат вывода

  • 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

Теги

Нужно войти, чтобы отправить решение.Войти