Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Прыгучее путешествие

(Время: 2 сек. Память: 16 Мб Сложность: 24%)

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

Тёма хочет посетить точки A1=(x1, y1), A2=(x2, y2), ..., An=(xn, yn) (можно считать, что изначально он находится в точке A1, затем прыгает в точку A2, потом в A3 и т.д.). Так же ему известно, что лягушка живет в точке B=(x, y) и имеет длину языка L. Таким образом, если после приземления Тёма оказывается на расстоянии не более L от точки B, то лягушка его съест, то есть лягушка может съесть Тёму только, когда он находится на земле. Во время полета съесть Тёму лягушка не может.

Ваша задача помочь Тёме определить, будет ли он съеден лягушкой или нет.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число N (1 ≤ N ≤ 105), координаты точки B и число L (0 ≤ L ≤ 5000). В следующих N строках записаны координаты точек Ai. Все координаты – это целые числа по модулю не превосходящие 104 .

Выходные данные

В выходной файл OUTPUT.TXT выведите «Yes», если кузнечик успешно завершит свое путешествие в точке An и не будет съеден в ней. Иначе выведите номер точки, после приземления в которую Тёму съест лягушка. Если Тёма может быть съеден лягушкой в нескольких точках, выведите точку, заданную раньше во входном файле (лягушка, разумеется, использует свой первый шанс, чтобы съесть кузнечика).

Примеры

INPUT.TXTOUTPUT.TXT
13 0 0 1
2 0
1 1
0 1
3
22 0 0 100
1 1
2 2
1
33 0 0 1
1 1
2 2
3 3
Yes

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru