The Moo Particle

题目描述

在 COWVID-19 疫情暴发期间，为了保护奶牛而进行隔离的 Farmer John 的奶牛们想出了一个缓解无聊的新方法：学习高等物理！事实上，奶牛们甚至发现了一种新的亚原子粒子，并将其命名为“moo 粒子”。

奶牛们正在进行一项涉及 $N$ 个 moo 粒子的实验（$1 \leq N \leq 10^5$）。第 $i$ 个粒子有一个由两个整数 $x_i$ 和 $y_i$ 描述的“自旋”，取值范围为 $-10^9 \ldots 10^9$（含端点）。有时两个 moo 粒子会发生相互作用。只有当两个粒子的自旋分别为 $(x_i, y_i)$ 和 $(x_j, y_j)$，并且满足 $x_i \leq x_j$ 且 $y_i \leq y_j$ 时，它们才可能发生相互作用。在这些条件下，可能会恰好有一个粒子消失（另一个粒子不发生任何变化）。在任意时刻，最多只会发生一次相互作用。

奶牛们想知道：在经过某种任意的相互作用序列之后，可能剩下的 moo 粒子数量的最小值是多少。

输入格式

第一行包含一个整数 $N$，表示初始 moo 粒子的数量。 接下来 $N$ 行每行包含两个用空格分隔的整数，表示一个粒子的自旋。每个粒子的自旋都互不相同。

输出格式

输出一个整数，表示在经过某种任意的相互作用序列之后，可能剩下的 moo 粒子数量的最小值。

4
1 0
0 1
-1 0
0 -1

1

3
0 0
1 1
-1 3

2

提示

一种可能的相互作用序列： 粒子 1 和 4 相互作用，粒子 1 消失。 粒子 2 和 4 相互作用，粒子 4 消失。 粒子 2 和 3 相互作用，粒子 3 消失。 最后只剩下粒子 2。

粒子 3 无法与另外两个粒子中的任意一个相互作用，因此它必须保留。粒子 1 和 2 中至少也必须有一个保留。

评分： 测试点 3-6 满足 $N\le 1000$。 测试点 7-12 没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2020|Silver

来源

USACO|2020|Silver