Məsələlər
Бильярд
Бильярд
Имеется бильярдный стол. Игровое поле имеет прямоугольную форму. Бильярдное поле имеет специальный вид, так как оно не имеет лунок, а игровая область окружена упругим бортом.
Вам удалось создать ультра-точный бильярд, в который играет робот. После расположения шаров на столе машина ударяет один из этих шаров. Шар, по которому ударили, останавливается после прохождения расстояния в \textbf{10000 }единиц.
Когда шар ударяется о борт стола, его направление движения зеркально отражается. Когда шар попадает в угол, он меняет свое направление на противоположное.
Вам следует выяснить, какой шар первым столкнется с мячом, который ударил робот.
\InputFile
Состоит из нескольких тестов. Количество тестов не более \textbf{100}. Каждый тест имеет следующий формат:
\textbf{n}
\textbf{w h r v_x v_y}
\textbf{x_1 y_1}
\textbf{...}
\textbf{x_n y_n}
Первая строка содержит количество шаров \textbf{n }(\textbf{2 }≤ \textbf{n }≤ \textbf{11}) на столе. Следующая строка содержит пять целых чисел \textbf{w}, \textbf{h}, \textbf{r}, \textbf{v_x}, \textbf{v_y}, разделенных пробелом, где \textbf{w }и \textbf{h }(\textbf{4 }≤ \textbf{w}, \textbf{h }≤ \textbf{1000}) - ширина и длина игровой области стола, \textbf{r }(\textbf{1 }≤ \textbf{r }≤ \textbf{100}) - радиус шаров. Робот ударяет шар в направлении вектора (\textbf{v_x}, \textbf{v_y}) (\textbf{-10000} ≤ \textbf{v_x}, \textbf{v_y} ≤ \textbf{10000}, (\textbf{v_x}, \textbf{v_y}) ≠ (\textbf{0}, \textbf{0})).
Следующие \textbf{n }строк задают положения шаров. Каждая строка содержит два целых числа (\textbf{x_i}, \textbf{y_i}) - положение центра \textbf{i}-го шара на столе в начальном состоянии (\textbf{r }< \textbf{x_i} < \textbf{w - r}, \textbf{r }< \textbf{y_i} < \textbf{h - r}). (\textbf{0}, \textbf{0}) задает положение северо-западного угла игровой области, а (\textbf{w}, \textbf{h}) задает положение юго-восточного угла игровой области. Считайте, что изначально шары не касаются друг друга и борта.
Робот всегда ударяет первый шар в списке. Входные данные корректны.
Последняя строка содержит ноль и не обрабатывается.
\OutputFile
Для каждого теста вывести индекс шара, который первым столкнется с шаром, который ударит робот. Если столкновения не произойдет до его остановки, то вывести "\textbf{-1}".
Первое столкновение произойдет не более чем с одним шаром.
Если \textbf{r }изменить на \textbf{eps }(\textbf{eps }< \textbf{10^\{-9\}}), то номер шара, о который произойдет первый удар, не изменится.
Giriş verilənləri #1
3 26 16 1 8 4 10 6 9 2 9 10 3 71 363 4 8 0 52 238 25 33 59 288 0
Çıxış verilənləri #1
3 -1