eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Турист

Турист

Турист путешествует пешком вдоль координатной оси \textbf{Ox}. Идти можно в любом из двух возможных направлений и с любой скоростью, не превышающей \textbf{V}, в том числе находиться на месте. Из газетных анонсов он знает, что в момент \textbf{t_1} в точке с координатой \textit{\textbf{x}}\textbf{_1} состоится одно интересное событие, в момент \textbf{t_2} в точке с координатой \textbf{x_2} - еще одно, и т. д., до (\textbf{x_N}, \textbf{t_N}). Интересные события достаточно кратковременны, их можно считать мгновенными. Считается, что турист посетил событие \textbf{i}, если в момент \textbf{t_i} он находился в точке с координатой \textbf{x_i}. Напишите программу, которая найдет максимальное количество событий, которые сможет посетить турист, для таких двух предположений: \begin{itemize} \item сначала движения (в момент времени \textbf{0}) турист находится в точке \textbf{0}; \item турист может выбрать начальную точку, из которой он стартует. \end{itemize} \InputFile Первая строка содержит единственное натуральное число \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{100 000}) - количество интересных событий. Последующие \textbf{N} строк содержат по два целых числа \textbf{x_i} и \textbf{t_i} - координату и момент времени события с номером \textbf{i}. Последняя (\textbf{N+2})-ая строка файла содержит единственное целое число \textbf{V} - значение максимальной скорости движения туриста. Все значения \textit{\textbf{x_i}} принадлежат диапазону \textbf{-10^8} ≤ \textbf{x_i} ≤ \textbf{10^8}, все значения \textbf{t_i} принадлежат диапазану \textbf{1} ≤ \textbf{t_i} ≤ \textbf{10^6}, значение \textbf{V} принадлежит диапазону \textbf{1} ≤ \textbf{V} ≤ \textbf{1000}. Во входных данных возможны различные события, имеющие одинаковую координату \textbf{x} или одинаковое время \textbf{t}, но невозможны различные события, имеющие одинаковые \textbf{x} и \textbf{t} одновременно. \OutputFile Единственная строка должна содержать два целых числа -- максимально возможное количество событий, которые турист может посетить, если он начнет движение в момент \textbf{0} из точки \textbf{0}, затем максимально возможное количество событий, которые турист может посетить, самостоятельно выбрав точку старта.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
-1 1
42 7
40 8
2
Выходные данные #1
1 2

Объяснение: Выйдя в момент 0 из точки 0, турист может успеть только на первое событие. Выйдя из точки 42, турист может посетить второе и третье события.

Автор Илья Порублев
Источник 2011 XXIV Всеукраинская олимпиада по информатике, Черкассы, Март 26 - 31, тур 1