Задача №1876. Снег
Вчера в королевстве был снегопад, а сегодня все его жители собрались, чтобы устроить народные гуляния. Результатом большого веселья стал огромный снежный ком посреди центральной площади. Глава королевства попросил Васю убрать это безобразие за город, чтобы оно не мешало дальнейшим развлечениям. Для этого требуется перекатить снежный ком, что требует некоторых усилий.
Для простоты представим, что действие происходит в двумерном пространстве, путь от центральной площади за город представляет собой отрезок прямой \([0, \, EndX]\), а снежный ком — строго выпуклый многоугольник. Одно Васино усилие позволяет перекатить ком на следующую грань (если занумеровать грани последовательно с \(1\) до \(N\), то если текущая грань \(i = N\), то следующая будет с номером \(1\), а иначе — с номером \(i + 1\)).
Помогите Васе определить, сколько усилий ему потребуется приложить, чтобы снежный ком оказался за городом. Считается, что снежный ком покинул пределы города, если текущие координаты по оси \(X\) обоих концов грани, на которой он лежит, не меньше \(EndX\).
В первой строке входного файла записаны два целых числа. Первое из них — \(N\) (\(3 \le N \le 80\,000\)) — количество вершин снежного кома. Второе — координата конца города \(EndX\) (\(0 \le EndX \le 10^9\)).
Далее следует \(N\) описаний вершин снежного кома в начальном положении, каждое из которых представляет собой две целочисленные координаты \(X_i\) и \(Y_i\). Гарантируется, что \(X_1 = 0\), \(Y_1 = 0\), \(Y_2 = 0\), \(X_2 > 0\), все \(Y_i\) неотрицательны и не превышают \(10^9\), все \(X_i\) по модулю не превышают \(10^9\), а порядок вершин во входном файле совпадает с обходом против часовой стрелки вершин снежного кома.
Гарантируется, что в предпоследний и последний моменты времени расстояния между концами грани, на которой лежит снежный ком, и точкой \(EndX\) будут \(\ge 0,1\) (то есть у вас не должно возникнуть проблем с точностью).
В выходной файл выведите единственное число — количество усилий, которое Васе потребуется приложить, чтобы снежный ком оказался за городом.
4 9 0 0 2 0 2 2 0 2
5