Нити на станке для ковров
На раме станка для ковров по кругу вбиты гвозди, пронумерованные по часовой стрелке числами от 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.
Комментарии