P14773 [ICPC 2024 Seoul R] Square Stamping

平面上有 $n$ 个点，它们的 $y$ 坐标只能是 $-9999$、$0$ 或 $9999$。令 $P$ 为这 $n$ 个点的集合。你的任务是用最少数量的全等且边与坐标轴平行的正方形来包围 $P$ 中的所有点。每个这样的正方形边长为 $10,000$。作为一个平面子集，每个正方形包含其内部及边界上的所有点。

你的程序需要从标准输入读取数据。输入的第一行包含一个整数 $n$ ($1 \leq n \leq 300,000$)，表示集合 $P$ 中点的数量。接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$，分别表示 $P$ 中一个点的 $x$ 坐标和 $y$ 坐标，满足 $-10^9 \leq x \leq 10^9$ 且 $y \in \{-9999, 0, 9999\}$。你可以假设所有 $n$ 个输入点都是互不相同的。

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含一个整数，表示可能存在的最小数 $t$，使得存在 $t$ 个边长为 $10,000$ 且边与坐标轴平行的正方形，它们的并集能够包围 $P$ 中的所有输入点。