Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1330. Выше гор могут быть только горы
Вычислительная геометрияСтеки, очереди
Олимпиадные задачи на русском языке
| 22/04/2001 | Региональная олимпиада Информатика-2001 (3) |
| 09/12/2010 | Сборы 31 (2C) |
| 25/03/2013 | Занятие 21 (B) |
Ограничения: время – 100ms/1s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Горную вершину можно увидеть на
фоне неба, если только она не скрывается за другой горой или
ее контур не скрыт на фоне другой горы. Предположим,
что склоны всех гор имеют наклон в `45°`, и известны координаты
и высоты вершин всех гор. Требуется определить
количество видимых горных вершин.
Во входном файле в первой строке целое число `N` (`1\ ≤\ N\ ≤\ 10\ 000`).
Далее идет `N` строк, по два целых числа через пробел в каждой строке:
координата `x_i` вершины (`0\ ≤\ x_i\ ≤\ 30\ 000`) и ее высота `y_i` (`1\ ≤\ y_i\ ≤\ 10\ 000`),
последовательность вершин является упорядоченной по возрастанию
координаты `x`: `x_1\ ≤\ x_2\ ≤\ …\ ≤\ x_N`.
В выходной файл вывести количество видимых вершин.
Пример ввода
4 6 5 12 3 16 9 21 4
Пример вывода
2
