3391. [USACO20 Open Silver]The Moo Particle

【题目描述】

在 COWVID-19 爆发期间 Farmer John 的奶牛们为了安全进行了隔离，她们想到了一种全新的方式缓解无聊：研究高等物理！事实上，她们甚至成功发现了一种新的亚原子粒子，她们将其命名为“哞粒子”。

奶牛们正在进行一项有关 $N$ 个哞粒子的实验（$1 \leq N \leq 10^5$）。粒子 $i$ 的“自旋”可以用范围在 $-10^9 \ldots 10^9$ 之间的两个整数 $x_i$ 和 $y_i$ 来描述。有时两个哞粒子会发生相互作用。自旋为 $(x_i, y_i)$ 和 $(x_j, y_j)$ 的两个粒子之间仅当 $x_i \leq x_j$ 并且 $y_i \leq y_j$ 时会发生相互作用。在这些条件下，有可能这两个粒子中的一个会消失（另一个粒子不会发生任何变化）。在任意给定的时刻，至多只有一次相互作用会发生。

奶牛们想要知道在经过一些任意的相互作用之后剩余的哞粒子的最小数量。

【输入格式】

输入的第一行包含一个整数 $N$，为哞粒子的初始数量。以下 $N$ 行每行包含两个空格分隔的整数，为一个粒子的自旋。每个粒子的自旋各不相同。

【输出格式】

输出一个整数，为经过一些任意的相互作用之后剩余的哞粒子的最小数量。

【样例输入1】

4
1 0
0 1
-1 0
0 -1

【样例输出1】

1

【样例输入2】

3
0 0
1 1
-1 3

【样例输出2】

2

【样例解释】

样例 1 解释:

一个可能的相互作用顺序：

粒子 1 和 4 相互作用，粒子 1 消失。

粒子 2 和 4 相互作用，粒子 4 消失。

粒子 2 和 3 相互作用，粒子 3 消失。

仅留下粒子 2。

样例 2 解释:

粒子 3 不能与任何其他两个粒子相互作用，所以它必然会留下。

粒子 1 和 2 中必然留下至少一个。

【提示】

对于$ 50\% $的测试数据(测试点$ 1 \sim 6 $)，满足$ N \le 10^3 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Silver 组