Гонки за драгоценностями
Гонки за драгоценностями
Вы играете в гоночную игру. Ваш персонаж стартует с оси x (y = 0) и двигается по гоночной дорожке, ограниченной прямыми x = 0 и x = w. Вы можете начать гонку в любой координате находящейся в границах трека. Финишная линия находится на прямой y = h, игра заканчивается при достижении этой линии. Вы двигаетесь с фиксированной вертикальной скоростью v, при этом Вы можете управлять своей горизонтальной скоростью, устанавливая ее равной любой величине между -v / r и v / r, изменяя ее в любой момент времени.
В определенных точках на гоночной трассе расположены n драгоценных камней. Какое максимальное количество драгоценных камней Вы сможете собрать?
Входные данные
Первая строка содержит четыре целых числа n, r, w и h (1 ≤ n ≤ 105
, 1 ≤ r ≤ 10, 1 ≤ w, h ≤ 109
). Каждая из следующих n строк содержит два целых числа xi
и yi
, описывающие координаты i-го камня (0 ≤ xi
≤ w, 0 < yi
≤ h). В каждой точке находится не более одного камня.
Входные данные не содержат значение v.
Выходные данные
Выведите максимальное количество драгоценных камней, которое можно собрать во время гонки.
5 1 10 10 8 8 5 1 4 6 4 7 7 9
3
5 1 100 100 27 75 79 77 40 93 62 41 52 45
3