Модуль: Метод сканирующей прямой (scanline)


Задача

4 /4


Частица Му


Задача

Углубившись на карантине в изучение физики, коровы открыли "му-частицы"
В настоящий момент они проводят эксперимент с N "му-частицами" (1 ≤N ≤ 105). Частица i имеет "спин", описываемый двумя целыми числами xi и yi в диапазоне −109…109 включительно. Иногда две "му-частицы" взаимодействуют. Это может случиться только с такими частицами со спинами (xi,yi) и (xj,yj) у которых xi≤xj и yi≤yj. При этих условиях ровно одна из этих частиц исчезает (а с другой ничего не случится). В каждый момент времени может случиться не более одного взаимодействия.

Коровы хотят узнать минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.

Входные данные
Первая строка содержит одно целое число N, начальное число "му-частиц". Каждая из последующих N строк содержит два разделённых пробелом целых числа, определяющих спин этой частицы. Все спины различны.
Выходные данные
Одно целое число, минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.
Примеры
Входные данные Выходные данные Примечание
1 4
1 0
0 1
-1 0
0 -1
1 Одна из возможных последовательностей взаимодействий:

Частицы 1 и 4 взаимодействуют, частица 1 исчезает.
Частицы 2 и 4 взаимодействуют, частица 4 исчезает.
Частицы 2 и 3 взаимодействуют, частица 3 исчезает.
Только частица 2 остаётся.
2 3
0 0
1 1
-1 3
2 Частица 3 не может взаимодействовать ни с одной из других частиц, поэтому она должна остаться. Одна из частиц 1 и 2 тоже должна остаться.

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя