P6909: Moo粒子
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
在 COWVID-19
爆发期间 Farmer John 的奶牛们为了安全进行了隔离，她们想到了一种全新的方式缓解无聊：研究高等物理！事实上，她们甚至成功发现了一种新的亚原子粒子，她们将其命名为“哞粒子”。
奶牛们正在进行一项有关 N
个哞粒子的实验（1≤N≤10^5
）。粒子 i
的“自旋”可以用范围在 −10
^9…10
^9
之间的两个整数 xi 和 yi 来描述。有时两个哞粒子会发生相互作用。自旋为 (xi,yi) 和 (xj,yj) 的两个粒子之间仅当 xi≤xj 并且 yi≤yj 时会发生相互作用。在这些条件下，有可能这两个粒子中的一个会消失（另一个粒子不会发生任何变化）。在任意给定的时刻，至多只有一次相互作用会发生。
奶牛们想要知道在经过一些任意的相互作用之后剩余的哞粒子的最小数量。
【
输入格式】
（文件名：moop.in
）：
输入的第一行包含一个整数 N
，为哞粒子的初始数量。以下 N
行每行包含两个空格分隔的整数，为一个粒子的自旋。每个粒子的自旋各不相同。
【
输出格式】
（文件名：moop.out
）：
输出一个整数，为经过一些任意的相互作用之后剩余的哞粒子的最小数量。
【
输入样例】
：
4
1 0
0 1
-1 0
0 -1
【
输出样例】
：
1
【样例说明】
一个可能的相互作用顺序：
1.粒子 1
和 4 相互作用，粒子 1 消失。
2.粒子 2
和 4 相互作用，粒子 4 消失。
3.粒子 2
和 3 相互作用，粒子 3 消失。
仅留下粒子 2
。
【
输入样例】
：
3
0 0
1 1
-1 3
【
输出样例】
：
2
【样例说明】
粒子 3
不能与任何其他两个粒子相互作用，所以它必然会留下。粒子 1 和 2 中必然留下至少一个。
【
测试点性质】
：
测试点 3-6
满足 N≤1000。
测试点 7-12
没有额外限制。