eolymp
bolt
Try our new interface for solving problems
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 Выведите одно число -- наименьшее количество преобразователей, необходимое для того, чтобы луч дошёл до конца туннеля.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4
1 1
2 1
3 2
4 1
Çıxış verilənləri #1
1