Олимпиадный тренинг

Задача . Hill Walk


Задача

Темы: геометрия реализация графы

Имется N (1 <= N <= 100,000) холмов. Каждый холм имеет форму отрезка из точки (x1, y1) в точку (x2, y2) где x1 < x2 и y1 < y2. Никакие из этих отрезков не пересекаются и не касаются даже в конечных точках. Кроме того, для первого холма справедливо (x1,y1) = (0,0).
Беси начинает свой путь в точке (0,0) на первом холме. Когда Беси попадает на холм, она карабкается вверх пока не достигнет конца холма. Затем она прыгает вниз. Если она приземлится на другой холм, она продолжит карабкание уже на этом холме, иначе она падает в бездну (где y=-бесконечности). Каждый холм (x1, y1) -> (x2, y2) необходимо рассматривать как содержащий точку (x1, y1), но не содержащий точку (x2, y2), поэтому Бэси приземляется на холм, если она падает на него сверху с позиции x = x1, но не приземлится на него, если она падает сверху с позиции x = x2.
Посчитайте общее количество холмов, которых Беси коснется в некоторой точке во время своего путешествия.
PROBLEM NAME: hillwalk
Формат входных данных
* Строка 1: Количество холмов, N.
* Строки 2..1+N: Строка i+1 содержит четыре целых числа (x1,y1,x2,y2) описывающих холм i. Каждое целое число находится в диапазоне 0..1,000,000,000.
Формат выходных данных
* Строка 1: Количество холмов, которых коснется Беси за время своего путешествия.
Примечание
Беси пройдется по холмам #1, #4, #3.
Примеры
№Входные данныеВыходные данные
1 
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7
 
3
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет