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

Світло в кінці тунеля

Світло в кінці тунеля

Тунель з квадратним перерізом складається з (\textbf{n}-\textbf{1}) секції. Підлога у кожній секції плоска і може бути нахилена догори або вниз. Координати (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), ..., (\textbf{x_n}, \textbf{y_n}) (\textbf{x_1} < \textbf{x_2} < ... < \textbf{x_n}) описують точки, у яких підлога тунеля починається, закінчується (перша і остання пари координат відповідно), або де секції з'єднуються. Висота тунеля рівна \textbf{1}, тобто стеля \textbf{i}-ї "точки з'єднання" має координати (\textbf{x_i}, \textbf{y_i} + \textbf{1}). У тунель направлено промінь лазера. Для того, щоб забезпечити передачу сигналу, можуть бути використанв перетворювачі світла, які можна встановити на границях секцій. Ці перетворювачі перенаправляють промінь у потрібному напрямку, причому не обов'язково з точки падіння променя (див. ілюстрацію). \includegraphics{https://static.e-olymp.com/content/84/844c68e4efffacd080981cdc74e691c04574099e.jpg} Так як перетворювачі перекривають тунель повністю і можуть бути встановлені лише на границях секцій, то кожен перетворювач однозначно задається своєю координатою - одним з чисел \textbf{x_1}, \textbf{x_2}, ..., \textbf{x_n}. Визначіть мінімальну кількість перетворювачів, необхідних для того, щоб світло дійшло до кінця тунелю. Дотикання променем стінок тунелю не допускається. \InputFile \includegraphics{file:///C:/Temp/moz-screenshot-10.png} Перший рядок вхідного файлу містить ціле число \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{1000}). Наступні \textbf{N} рядків містять \textbf{2} дійсних числа, заданих у типі \textit{extended} -- координати \textbf{x_i} і \textbf{y_i} (\textbf{-10000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10000}). \OutputFile Виведіть одне число -- найменшу кількість перетворювачів, необхідних для того, щоб промінь дійшов до кінця тунелю.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4
1 1
2 1
3 2
4 1
Вихідні дані #1
1