Задача D. Новогодний пузырь ≡
| Автор: | А. Кленин | Ограничение времени: | 5 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 200 Мб | |
| Выходной файл: | output.txt |
Условие
Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0),
а правого верхнего — (1000, 1000).
С потолка зала свешивается мишура в виде N прямых тонких вертикальных лент
с координатами нижних концов (xi, yi).
Один из гостей запустил мыльный пузырь радиуса R.
Первоначально центр пузыря находился в точке (x, R).
Пузырь полетел вертикально вверх до столкновения с
лентой мишуры или потолком, после чего лопнул.
Требуется определить, с чем именно он столкнулся.
Формат входного файла
В первой строке входного файла содержатся числа N R x, в следующих N строках содержатся вещественные числа xi yi. Числа в строке разделены пробелами. Значения всех xi во входном файле различны.Формат выходного файла
В выходном файле должно содержаться единственное число — номер ленты (во входном файле), либо 0 (нуль), если пузырь долетел до потолка. Если пузырь одновременно столкнулся с несколькими лентами (и, возможно, потолком), вывести номер самой левой ленты.Ограничения
0 ≤ N ≤ 100, 0 < R ≤ 50, R ≤ x < 1000 − R
0 < xi < 1000, 0 < yi < 1000
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|