Задача №111766. Турист
Турист путешествует пешком вдоль координатной оси Ox . Идти можно в любом из двух возможных направлений и с любой скоростью, не превышающей V , в том числе находиться на месте. Из газетных анонсов он знает, что в момент t 1 в точке с координатой x 1 состоится одно интересное событие, в момент t 2 в точке с координатой x 2 — еще одно, и так далее, до ( x N , t N ). Интересные события достаточно кратковременны, их можно считать мгновенными. Считается, что турист посетил событие i , если в момент t i он находился в точке с координатой x i .
Напишите программу, которая найдет максимальное количество событий, которые сможет посетить турист, для таких двух предположений:
А) в начале движения (в момент времени 0 ) турист находится в точке 0 ;
Б) турист может выбрать начальную точку, из которой он стартует.
Первая строка входного файла содержит единственное натуральное число N ( 1 ≤ N ≤ 100000 ) — количество интересных событий.
Последующие N строк содержат по два целых числа x i и t i — координату и момент времени события с номером i .
Последняя ( N + 2 )-ая строка файла содержит единственное целое число V — значение максимальной скорости движения туриста.
Все значения x i принадлежат диапазону - 10 8 ≤ x i ≤ 10 8 , все значения t i принадлежат диапазону 1 ≤ t i ≤ 10 6 , значение V принадлежит диапазону 1 ≤ V ≤ 1000 .
Во входных данных возможны различные события, имеющие одинаковую координату x или одинаковое время t , но невозможны различные события, имеющие одинаковые x и t одновременно.
Единственная строка выходного файла должна содержать два целых числа –– максимально возможное количество событий, которые турист может посетить, если он начнет движение в момент 0 из точки 0 , затем максимально возможное количество событий, которые турист может посетить, самостоятельно выбрав точку старта.
Выйдя в момент 0 из точки 0 , турист может успеть только на первое событие. Выйдя из точки 42 , турист может посетить второе и третье события.
3 -1 1 42 7 40 8 2
1 2