eolymp
bolt
Try our new interface for solving problems
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\}}), то номер шара, о который произойдет первый удар, не изменится.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
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
Mənbə 2012 JAG Practice Contest for ACM-ICPC Asia Regional 2012, AtCoder, November 4; 2013 Petrozavodsk Winter Training Camp, January 26, Problem A