Məsələlər
Свет в конце туннеля
Свет в конце туннеля
Туннель с квадратным сечением состоит из (\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
Выведите одно число -- наименьшее количество преобразователей, необходимое для того, чтобы луч дошёл до конца туннеля.
Giriş verilənləri #1
4 1 1 2 1 3 2 4 1
Çıxış verilənləri #1
1