Задача №1684. Радиолокация
Вводится новый авиарейс между городами \(A\) и \(B\). Самолет будет лететь строго по прямой, соединяющей эти города. На протяжении всего пути необходимо, чтобы за самолетом могли наблюдать с земли при помощи радаров. Однако, радиус действия радаров ограничен, и равен \(R\). Хуже того, радарные станции имеются только в определенных точках (например, других населенных пунктах). Руководство авиакомпании желает выяснить: можно ли следить за самолетом на протяжении всего пути из \(A\) в \(B\). Если это возможно, то каким минимальным количеством уже имеющихся радаров можно для этого обойтись. Самолет, находящийся на границе действия радара является видимым, то есть если расстояние от радара до самолета точно равно \(R\), то считается что радар еще действует.
сначала вводятся координаты точек \(A\) и \(B\) (целые числа, по модулю не превышают 1000), затем вводится число \(N\) (натуральное, не превышает 20) – количество уже построенных радаров, затем следует число \(R\) – радиус действия радара (натуральное, не превышает 1000). Затем вводится \(N\) пар чисел – координаты уже построенных радаров (целые, по модулю не превышают 1000). Наличие радаров в городах \(A\) и \(B\) возможно, но необязательно.
выведите минимальное количество радаров, которое надо задействовать для сопровождения самолета на всем пути. Если сопровождение имеющимися средствами невозможно – выведите число -1.
0 0 1 1 1 1 5 5
-1
0 0 10 0 3 5 0 0 5 0 10 0
1