printРабочее место участника

printЗадачи

1710. Космический кегельбан

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.
Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом `r` метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют `n` рядов, в первом ряду стоит одна кегля, во втором – две, и так далее. В последнем `n`-м ряду стоит `n` кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке `(0, 0)`. Центры кеглей во втором ряду находятся в точках `(–1, 1)` и `(1, 1)`. Таким образом, центры кеглей в `i`-м ряду находятся в точках с координатами `(–(i – 1), i – 1)`, `(–(i – 3), i – 1)`, …, `(i – 1, i – 1)`.
Игра происходит следующим образом. Используется шар с радиусом `q` метров. Игрок выбирает начальное положение центра шара `(x_c, y_c)` и вектор направления движения шара `(v_x, v_y)`. После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора `(v_x, v_y)`. Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.
На рисунке приведен пример расположения кеглей для `r = 500`, `n = 4` и шара для `q = 1000`, `x_c = –2`, `y_c = –2``v_x = 1`, `v_y = 1`.

21068.png

Требуется написать программу, которая по заданным радиусу кегли `r`, количеству рядов кеглей `n`, радиусу шара `q`, его начальному положению `(x_c, y_c)` и вектору направления движения `(v_x, v_y)` определяет количество кеглей, сбитых шаром.
Формат входного файла
Первая строка входного файла содержит два целых числа: `r` и `n`, разделенных ровно одним пробелом (`1 ≤ r ≤ 700`, `1 ≤ n ≤ 200 000`).
Вторая строка входного файла содержит целое число `q` (`1 ≤ q ≤ 10^9`).
Третья строка входного файла содержит два целых числа `x_c` и `y_c`, разделенных ровно одним пробелом (`–10^6\ ≤ "xc" ≤ 10^6`, `–10^6\ ≤ "yc"`, `1000*y_c\ <\ –(r + q)` ).
Четвертая строка входного файла содержит два целых числа `v_x` и `v_y`, разделенных ровно одним пробелом (`–10^6\ ≤ v_x ≤ 10^6`, `0 < v_y ≤ 10^6`).
Формат выходного файла
Выходной файл должен содержать одно целое число – количество сбитых кеглей.

Пример ввода

500 4
1000
-2 -2
1 1

Пример вывода

7
Пояснения к примеру
Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).

21069.png

Система оценивания
Правильные решения для тестов, в которых `1 ≤ n ≤ 1000` и `"vx" = 0`, будут оцениваться из 20 баллов.
Правильные решения для тестов, в которых `1 ≤ n ≤ 1000` и `v_x ≠ 0`, будут оцениваться еще из 20 баллов.
Правильные решения для тестов, в которых `1000 < n ≤ 200 000` и `v_x = 0`, будут оцениваться еще из 20 баллов.
Чтобы получить оставшиеся 40 баллов, решение должно правильно работать также для тестов, в которых `1000 < n ≤ 200 000` и `v_x ≠ 0`.
Источник: региональный этап Всероссийской олимпиады по информатике 2011/2012, http://neerc.ifmo.ru/school/
loading