Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1124. Изрезанная бумага
Вычислительная геометрияПоиск в глубину (DFS)
Олимпиадные задачи на русском языке
| 05/01/2005 | Областная олимпиада школьников по информатике (личное первенство) (5) |
Ограничения: время – 1s/2s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На листе бумаги выполнено несколько разрезов. Отрезки-разрезы имеют наклон только 0, 45, 90 и 135 градусов к оси ординат. Таким образом в одной точке могут пересекаться не более 4 отрезков. Отрезки, расположенные на одной прямой, не пересекаются. Разрезы не доходят до краев бумаги. Напишите программу, определяющую на сколько отдельных кусков был разрезан лист бумаги.
В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество разрезов. Далее следует `N` строк, в каждой строке четыре целых числа X1, Y1, X2, Y2 в диапазоне от 1 до 999, разделенных пробелами – координаты двух концов разреза. Координаты левого нижнего угла бумаги `(0,\ 0)`, а правого верхнего – `(1000,\ 1000)`.
В первой строке выходного файла вывести одно целое число – количество отдельных кусков бумаги, на которые был разделен лист заданными разрезами.
Пример ввода
4 100 300 800 300 100 200 700 800 400 300 400 900 600 700 600 100
Пример вывода
3
