Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Муза, скажи мне о том многоопытном муже, который\
Долго скитался с тех пор, как разрушил священную Трою,\
Многих людей города посетил и обычаи видел,\
Много духом страдал на морях, о спасеньи заботясь\
Жизни своей и возврате в отчизну товарищей верных.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 1
Эллада состоит из `N` островов, пронумерованных от `1` до `N`. Одиссей спешит из Трои (остров 1) домой на Итаку (остров `N`). Из-за
несовершенства методов древнегреческой навигации корабль Одиссея плавает только по прямым отрезкам, соединяющим острова, и за
один переход преодолевает расстояние не больше `T`. Если Одиссей останавливается на острове, то вынужден долгие недели пировать в
гостях у местного царя и рассказывать ему о своих подвигах, поэтому желательно останавливаться как можно реже. Но если царь заметит,
что Одиссей проплыл поблизости от его острова (на расстоянии `D` или меньше) и не остановился, то это будет сочтено
за величайшее оскорбление, за Одиссеем пошлют погоню, и домой он вообще не попадет. Помогите Одиссею предсказать, как
скоро он сможет вернуться к любимой жене Пенелопе!
В первой строке входного файла указаны три целых числа: количество островов `N` (`1<=N<=1000`),
максимальная дальность перехода `T` (`1<=T<=1000000`) и дальность обзора `D` (`1<=D<=1000`).
Затем следует `N` строк -- описания островов. Каждая строка содержит два целых числа `x_i` и `y_i` -- координаты
соответствующего острова (`-1000<=x_i,y_i<=1000`). Острова считаются точками. Гарантируется, что
все острова расположены на расстоянии строго больше `D` друг от друга.
Выведите одно целое число -- минимальное количество переходов между островами, которое придется выполнить Одиссею.
Каждый переход должен быть прямым, иметь длину не более `T` и не проходить на расстоянии `D` или меньше от любого другого острова.
```sample Пример ввода 1
6 5 1
0 4
2 5
3 3
3 0
4 4
6 4
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
2 1 1
0 0
1 1
```
```sample Пример вывода 2
-1
```
Пояснение к примеру 1. С острова 1 можно плыть к островам 2, 3 и 4. Остров 6 слишком далеко, а путь до острова 5 находится слишком близко (на расстоянии ровно 1) к острову 2.
С островов 2 и 3 прямой переход к острову 6 невозможен, так как он будет пролегать слишком близко к острову 5. Но с острова 4 до острова 6 добраться можно. Получаем единственный путь из двух переходов: 1->4->6.
Начало
Рабочее место участника
Вычислительная геометрия