Нити на станке для ковров


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На раме станка для ковров по кругу вбиты гвозди, пронумерованные по часовой стрелке числами от 1 до 10⁹. Мастерица натянула m нитей; нить i — это отрезок прямой между гвоздями a[i] и b[i]. Несколько нитей могут начинаться на одном гвозде, но никакие две нити не соединяют одну и ту же пару гвоздей. Гвозди расставлены так, что никакие три нити не проходят через одну точку внутри круга.

Нити делят круг на части. Сколько получилось частей?

Рисунок

Входные данные

В первой строке — число m (1 ≤ m ≤ 5 · 10⁵). В каждой из следующих m строк — два различных целых числа a[i] b[i] (1 ≤ a[i], b[i] ≤ 10⁹).

Выходные данные

Выведите количество частей.

Пример 1

Вход:

4
1 5
3 7
1 3
8 6

Выход:

7

Пояснение

Четыре нити на рисунке: нити 1–5 и 3–7 пересекаются, нить 1–3 делит с ними гвозди, но не пересекает их, нить 6–8 пересекает 3–7. Пересечений внутри круга два, частей 1 + 4 + 2 = 7.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 500.

Подсказка

Формула Эйлера для плоских графов: V − E + F = 2.


Комментарии

Еще нет ни одного комментария.