Задача 7 регионального этапа Всероссийской олимпиады школьников по информатике 2011/2012 учебного года (offline)

Задачу добавил: alef

Успешно сдано решений: 5

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

Входной файл:  input.txt
Выходной файл:   output.txt
Ограничение по времени:    2 секунды
Ограничение по памяти:    256 мегабайт

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.
Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом 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, yc) и вектор направления движения шара (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.

 
Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению (x_c, y_c) и вектору направления движения (v_x, v_y) определяет количество кеглей, сбитых шаром.

Формат входного файла

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 ≤ r ≤ 700, 1 ≤ n ≤ 200 000).
Вторая строка входного файла содержит целое число q (1 ≤ q ≤ 10⁹).
Третья строка входного файла содержит два целых числа x_c и y_c, разделенных ровно одним пробелом (–10⁶≤ x_c ≤ 10⁶, –10⁶≤ y_c , 1000×y_c < –(r + q) ).
Четвертая строка входного файла содержит два целых числа v_x и v_y, разделенных ровно одним пробелом (–10⁶≤ v_x ≤ 10⁶, 0 < v_y ≤ 10⁶).

Формат выходного файла

Выходной файл должен содержать одно целое число — количество сбитых кеглей.

Пример входного файла
500 4
1000
-2 -2
1 1   

Пример выходного файла
7

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

Система оценивания
Правильные решения для тестов, в которых 1 ≤ n ≤ 1000 и v_x = 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.
 

Сдать задачу

Задать вопрос жюри по этой задаче