P13648 [NOISG 2016] Rock Climbing

在某一天，Panda 先生和猫咪 Rar 决定去攀岩。攀岩墙上有 $N$ 块岩石。第 $i$ 块岩石位于距离墙底 $Y_i$ 的高度，距离墙中心右侧 $X_i$ 个单位的位置。如果 $X_i$ 为负，则表示在中心左侧。所有岩石的位置都不相同。 为了考验 Panda 先生的攀岩技巧，猫咪 Rar 给他出了一个挑战。挑战内容如下： 1. 在 $N$ 块岩石中，猫咪 Rar 会选出 $K$ 块岩石组成一个集合 $R$。 2. 为了赢得挑战，Panda 先生需要从集合 $R$ 中任选一对岩石 $(A, B)$。Panda 先生可以自由选择任意一对岩石，只要 $A \neq B$ 且两块岩石都在集合 $R$ 中。 3. Panda 先生将从第一块岩石 $(A)$ 出发，尝试到达第二块岩石 $(B)$。在从 $A$ 到 $B$ 的过程中，他可以经过其他岩石，无论这些岩石是否在集合 $R$ 中。 4. 但是，每块岩石都有一个滑溜系数 $S_i$。滑溜系数越高，越难从这块岩石伸展到远处的岩石而不滑落。此外，猫咪 Rar 只允许他向上攀爬。更准确地说，从第 $i$ 块岩石移动到第 $j$ 块岩石，需要满足 $\max(|X_i - X_j|, |Y_i - Y_j|) \leq \max(S_i, S_j)$ 且 $Y_i < Y_j$。 5. 如果 Panda 先生能够选出一对岩石 $(A, B)$，使得他能从岩石 $A$ 到达岩石 $B$，则他赢得挑战。如果无法做到，则挑战失败。 请参考样例输入输出以获取更多细节。 当然，Panda 先生知道有很多岩石对无法完成挑战。他想要找到最小的 $K$，使得无论猫咪 Rar 如何选择岩石集合，他都能完成挑战。请你帮他找出这个值。

你的程序需要从标准输入读取数据。第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含三个整数，分别为 $X_i, Y_i, S_i$，表示第 $i$ 块岩石的信息。

你的程序需要输出一行，一个整数，表示使 Panda 先生总能完成挑战所需的最小岩石数。如果 Panda 先生永远无法完成挑战，输出 $-1$。

### 样例解释 1 当 $K = 2$ 时，存在某些岩石子集使 Panda 先生无法完成挑战。例如，如果猫咪 Rar 选择 $(-1, 1)$ 和 $(2, 2)$ 这两块岩石组成集合 $R$，Panda 先生无法完成挑战。Panda 先生无法从 $(2, 2)$ 移动到 $(-1, 1)$，因为只能向上攀爬。Panda 先生也无法直接从 $(-1, 1)$ 移动到 $(2, 2)$，因为 $\max(|-1 - 2|, |1 - 2|) = 3 > \max(2, 1) = 2$。 另一种选择是尝试间接从 $(-1, 1)$ 到 $(2, 2)$。Panda 先生可以从 $(-1, 1)$ 攀爬到 $(0, 3)$，因为 $\max(|-1 - 0|, |1 - 3|) = 2 \leq \max(2, 1) = 2$。但他无法从 $(0, 3)$ 移动到 $(2, 2)$，因为必须向上攀爬。 此外，可以验证，对于任意 3 块岩石的集合，总能找到一对岩石使 Panda 先生完成挑战。例如，如果猫咪 Rar 选择 $(-1, 5)$、$(4, 4)$、$(-1, 1)$ 这三块岩石组成集合 $R$，Panda 先生可以选择 $(-1, 5)$ 和 $(-1, 1)$ 这对岩石。完成挑战的方法是从 $(-1, 1)$ 攀爬到 $(0, 3)$，再到 $(-1, 5)$。中间经过的岩石不需要在 $R$ 中。 ### 样例解释 2 本测试点仅适用于子任务 1、2 和 5。 如果猫咪 Rar 选择高度为 2 的两块岩石（即第 2 和第 3 块岩石），Panda 先生无法完成挑战，因为他只能向上攀爬。因此，只有当猫咪 Rar 选择所有岩石时，Panda 先生才能保证完成挑战。 ### 样例解释 3 本测试点仅适用于子任务 2、3、4 和 5。 即使猫咪 Rar 选择了所有岩石，Panda 先生也无法从一块岩石到达另一块岩石。因此，Panda 先生永远无法完成挑战。 ### 子任务 每个测试点的最大运行时间为 1.0 秒。你的程序将在以下输入范围内进行测试： | 子任务 | 分值 | $N$ | 其他限制 | | :-: | :-: | :-: | :-: | | 1 | 15 | $1 \leq N \leq 20$ | 所有 $S_i = 2 \times 10^6$ | | 2 | 29 | $1 \leq N \leq 20$ | 无其他限制 | | 3 | 17 | $1 \leq N \leq 500$ | 所有 $X_i = 0$，且所有 $S_i$ 相等 | | 4 | 19 | $1 \leq N \leq 500$ | 所有 $S_i = 1$，且所有 $Y_i$ 不是 3 的倍数 | | 5 | 20 | $1 \leq N \leq 500$ | 无其他限制 | 对于所有测试点，$-10^6 \leq X_i \leq 10^6$，$1 \leq Y \leq 10^6$，$1 \leq S_i \leq 2 \times 10^6$。 由 ChatGPT 4.1 翻译