Задача: Cow Crossings
Каждый день N (1 <= N <= 100,000) коров Фермера Джона переходят дорогу, расположенную в середине фермы. Рассмотрим карту фермы Джона на 2D-плоскости, дорога идет горизонтально, одна сторона дороги описывается прямой y=0, другая - прямой y=1.
Корова i пересекает дорогу, следуя по прямой из позиции (ai,0) на одной стороне в позицию (bi,1) на другой стороне. Все ai различны, так же как и все Bi. И все эти числа находятся в диапазоне -1,000,000...1,000,000.
ФД называет переход безопасным, если он не пересекается никакими другими переходами. Помогите ФД подсчитать количество безопасных переходов.
PROBLEM NAME: crossings
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i содержит целые числа ai и bi, описывающие путь коровы i.
Формат выходных данных
* Строка 1: Количество безопасных переходов.
Примечание
Переходы первой и третьей коров не пересекаются переходами никаких других коров. Переходы второй и четвертой коров пересекают друг друга.
Ваш ответ: