Більярд#4294
Маємо більярдний стіл. Ігрове поле має прямокутну форму. Це особливий стіл, оскільки він не має лунок, а ігрова область оточена пружним бортом.
Вам вдалося створити ультра-точний більярд, в який грає робот. Після розташування куль на столі, машина вдаряє одну з цих куль. Куля, по якій вдарили, зупиняється після проходження відстані в одиниць.
Коли куля вдаряється об борт столу, її напрямок руху дзеркально відображається. Якщо куля потрапляє в кут, вона змінює свій напрямок на протилежний.
Вам потрібно визначити, яка куля першою зіткнеться з тією, яку вдарив робот.
Вхідні дані складаються з кількох тестів. Кількість тестів не перевищує . Кожен тест має наступний формат:
n
w h r v_x v_y
x_1 y_1
...
x_n y_n
Перший рядок містить кількість куль (2 \le n \le 11) на столі. Наступний рядок містить п'ять цілих чисел , , , v_x, v_y, розділених пробілом, де і (4 \le w, h \le 1000) - ширина і довжина ігрової області столу, (1 \le r \le 100) - радіус куль. Робот вдаряє кулю в напрямку вектора (v_x, v_y) (-10000 \le v_x, v_y \le 10000, (v_x, v_y) \ne (0, 0)).
Наступні рядків задають положення куль. Кожен рядок містить два цілих числа (x_i, y_i) - положення центру -ї кулі на столі в початковому стані (r < x_i < w - r, r < y_i < h - r). задає положення північно-західного кута ігрової області, а задає положення південно-східного кута ігрової області. Вважайте, що спочатку кулі не торкаються одна одної і борту.
Робот завжди вдаряє першу кулю в списку. Вхідні дані коректні.
Останній рядок містить нуль і не обробляється.
Для кожного тесту виведіть індекс кулі, яка першою зіткнеться з кулею, яку вдарив робот. Якщо зіткнення не відбудеться до її зупинки, виведіть "-1".
Перше зіткнення відбудеться не більше ніж з однією кулею.
Якщо змінити на (eps < 10^{-9}), то номер кулі, об яку відбудеться перший удар, не зміниться.
Приклад 1