P7559 [JOISC 2021] IOI 熱の感染拡大 (Day1)

JOI 王国有 $N$ 个宫殿，第 $i$ 个宫殿坐标为 $(X_i,Y_i)$，每个宫殿居住着一个王子，第 $i$ 个宫殿里的王子为 $i$ 号王子。从第 $0$ 时刻开始，每个王子将会从自己的宫殿出发开始走动，他们可以选择东南西北： - 如果选择东，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x+t,y)$。 - 如果选择西，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x-t,y)$。 - 如果选择南，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y-t)$。 - 如果选择北，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y+t)$。 $t$ 不一定是整数。 方向不会给定，你可以自己规划。 不幸的是，$1$ 号王子染上了 IOVID-114514 病毒，在 $0$ 时刻只有 $1$ 号王子感染了该病毒。 IOVID-114514 病毒按照如下方式进行传播： - 如果某一个时刻 $a$ 号王子和 $b$ 号王子在同一个坐标上，且 $a$ 号王子感染了病毒，$b$ 号王子没有感染病毒，则 $a$ 号王子会将病毒传染给 $b$ 号王子。 IOVID-114514 病毒没有其他传染方式，可怜的国王 JOI 114514 世也没有发现治愈方法。 （消毒水也不能治愈！） JOI 114514 世想问问你求第 $10^{100}$ 个时刻的时候最多会有多少个王子感染 IOVID-114514 病毒。

第一行一个整数 $N$ 代表宫殿个数。 接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表一个宫殿的坐标。

一行一个整数代表答案。

#### 样例 1 解释  我们规划 $1$ 号王子向东，$2$ 号王子向西。 不难发现，不论怎么移动 $1$ 都无法与 $2$ 相遇，只有 $1$ 号王子一个感染者。 #### 样例 2 解释  我们规划 $1$ 号王子向东，$2$ 号王子向北，$3$ 号王子向西。 - 时刻 $0$，$1$ 号王子是感染者。 - 时刻 $1$，$1$ 号王子与 $2$ 号王子坐标重合，$2$ 号王子感染。 - 时刻 $2$，$2$ 号王子与 $3$ 号王子坐标重合，$3$ 号王子感染。 #### 样例 3 解释 我们规划 $1$ 号王子向北，$2$ 号王子向南。 - 时刻 $0$，$1$ 号王子是感染者。 - 时刻 $0.5$，$1$ 号王子和 $2$ 号王子坐标重合，$2$ 号王子感染。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$N \le 7$，满足性质 A。 - Subtask 2（8 pts）：$N \le 15$，满足性质 A。 - Subtask 3（6 pts）：$N \le 100$，满足性质 A 和 B。 - Subtask 4（6 pts）：$N \le 100$，满足性质 A。 - Subtask 5（12 pts）：$N \le 3000$。 - Subtask 6（32 pts）：满足性质 A。 - Subtask 7（31 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le X_i,Y_i \le 5 \times 10^8$，宫殿坐标互不重合。 其中性质分别为： - 性质 A：$X_i \ne X_j$，$Y_i \ne Y_j$。 - 性质 B：$1$ 号宫殿坐标为原点。 #### 说明 翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 B IOI 熱の感染拡大 (IOI Fever) 的英文版本](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/fever-en.pdf)。