AT_joisc2021_b IOI 熱の感染拡大 (IOI Fever)

JOI 王国有 $N$ 座编号从 $1$ 到 $N$ 的房屋。房屋 $i$ ($1 \leq i \leq N$) 的坐标是 $(X_i, Y_i)$。不同的房屋有不同的坐标。每座房屋住着一位居民。房屋 $i$ 的居民被称为居民 $i$。 JOI 王国开始了一个长假。在时刻 $0$，每位居民离开房屋，开始旅行。开始时，每位居民选择“东”、“西”、“南”、“北”中的一个方向作为旅行方向。居民将按以下方式旅行： - 如果居民 $i$ 选择“东”，则该居民以速度 $1$ 沿 $x$ 轴正方向移动。换句话说，在时刻 $t$ ($t \geq 0$)，居民 $i$ 的坐标变为 $(X_i + t, Y_i)$。 - 如果居民 $i$ 选择“西”，则该居民以速度 $1$ 沿 $x$ 轴负方向移动。换句话说，在时刻 $t$ ($t \geq 0$)，居民 $i$ 的坐标变为 $(X_i - t, Y_i)$。 - 如果居民 $i$ 选择“南”，则该居民以速度 $1$ 沿 $y$ 轴负方向移动。换句话说，在时刻 $t$ ($t \geq 0$)，居民 $i$ 的坐标变为 $(X_i, Y_i - t)$。 - 如果居民 $i$ 选择“北”，则该居民以速度 $1$ 沿 $y$ 轴正方向移动。换句话说，在时刻 $t$ ($t \geq 0$)，居民 $i$ 的坐标变为 $(X_i, Y_i + t)$。 不幸的是，在时刻 $0$，居民 $1$ 感染了新发现的传染病 IOI 热病。在时刻 $0$，除了居民 $1$ 没有其他感染者。IOI 热病在居民之间按以下方式传播： 假设在某个时刻，居民 $a$ ($1 \leq a \leq N$) 和居民 $b$ ($1 \leq b \leq N$) 具有相同的坐标，居民 $a$ 感染了 IOI 热病，而居民 $b$ 没有感染 IOI 热病。那么，居民 $b$ 会感染 IOI 热病。 IOI 热病不会通过其他方式传播。此外，由于 IOI 热病是一种无法治愈的疾病，感染的居民不会康复。 作为 JOI 王国的大臣，你需要估计如果居民们做出最坏可能的选择，将有多少居民会感染 IOI 热病。 编写一个程序，给定房屋的数量和每个房屋的坐标，计算在时刻 $10^{100}$ 时可能感染的最大居民数量。

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

输出在时刻 $10^{100}$ 时可能感染的最大居民数量。 ### 样例输入 #1 ``` 2 0 0 4 3 ``` ### 样例输出 #1 ``` 1 ``` ### 样例输入 #2 ``` 3 1 2 2 1 4 3 ``` ### 样例输出 #2 ``` 3 ``` ### 样例输入 #3 ``` 2 20 20 20 21 ``` ### 样例输出 #3 ``` 2 ``` ### 样例输入 #4 ``` 15 5 6 2 9 12 0 4 11 3 12 6 5 0 8 9 10 11 13 8 7 13 2 1 1 7 14 10 4 14 3 ``` ### 样例输出 #4 ``` 9 ``` ### 样例输入 #5 ``` 30 275810186 246609547 122805872 99671769 243507947 220373844 281305347 252104708 237805644 214671541 172469077 149334974 222589229 229887956 160653451 208404690 241378966 211098219 144302355 224755786 186392385 163258282 199129390 169928751 294937491 265736852 196096122 172962019 314342944 285142305 202720470 166337671 157037485 133903382 263858979 240724876 210720220 181519581 296402036 267201397 186021287 183036854 195081930 173976211 328293029 299092390 261195361 238061258 323595085 294394446 299933764 270733125 240976723 128081418 188501753 165367650 277832422 248631783 119896220 96762117 ``` ### 样例输出 #5 ``` 11 ```

#### 样例 1 解释 在这个样例输入中，房屋的位置如下。  例如，假设居民 $1$ 选择“东”，居民 $2$ 选择“西”。 那么，在任何时刻，居民 $1$ 和 $2$ 的坐标都不同。因此居民 $2$ 不会被感染。所以在时刻 $10^{100}$，只有居民 $1$ 被感染。感染人数为 $1$。 无论居民 $1$ 和 $2$ 如何选择方向，感染人数都不能超过 $1$。因此可能感染的最大居民数是 $1$，输出 $1$。 此样例输入满足子任务 1, 2, 3, 4, 5, 6, 7 的约束。 #### 样例 2 解释 在这个样例输入中，房屋的位置如下。  例如，假设居民 $1$ 选择“东”，居民 $2$ 选择“北”，居民 $3$ 选择“西”。那么 IOI 热病按以下方式传播： - 在时刻 $0$，只有居民 $1$ 被感染。 - 在时刻 $1$，居民 $1$, $2$, $3$ 的坐标分别是 $(2, 2)$, $(2, 2)$, $(3, 3)$。居民 $1$ 和 $2$ 的坐标相同。此时，居民 $1$ 感染了 IOI 热病，而居民 $2$ 没有感染。因此居民 $2$ 被感染。 - 在时刻 $2$，居民 $1$, $2$, $3$ 的坐标分别是 $(3, 2)$, $(2, 3)$, $(2, 3)$。居民 $2$ 和 $3$ 的坐标相同。此时，居民 $2$ 感染了 IOI 热病，而居民 $3$ 没有感染。因此居民 $3$ 被感染。 最终，感染人数变为 $3$。因为这是可能的最大值，所以输出 $3$。 此样例输入满足子任务 1, 2, 4, 5, 6, 7 的约束。 #### 样例 3 解释 假设居民 $1$ 选择“北”，居民 $2$ 选择“南”。那么 IOI 热病按以下方式传播： - 在时刻 $0$，只有居民 $1$ 被感染。 - 在时刻 $0.5$，居民 $1$ 和 $2$ 的坐标都是 $(20, 20.5)$。此时，居民 $1$ 感染了 IOI 热病，而居民 $2$ 没有感染。因此居民 $2$ 被感染。 最终，感染人数变为 $2$。因为这是可能的最大值，所以输出 $2$。 ### 子任务 1. (5 分) $N \leq 7$, $X_i \neq X_j$, $Y_i \neq Y_j$ ($1 \leq i < j \leq N$) 2. (8 分) $N \leq 15$, $X_i \neq X_j$, $Y_i \neq Y_j$ ($1 \leq i < j \leq N$) 3. (6 分) $N \leq 100$, $X_i \neq X_j$, $Y_i \neq Y_j$ ($1 \leq i < j \leq N$), $X_1 = 0$, $Y_1 = 0$ 4. (6 分) $N \leq 100$, $X_i \neq X_j$, $Y_i \neq Y_j$ ($1 \leq i < j \leq N$) 5. (12 分) $N \leq 3\,000$ 6. (32 分) $X_i \neq X_j$, $Y_i \neq Y_j$ ($1 \leq i < j \leq N$) 7. (31 分) 无额外约束 翻译自 [第２０回日本情報オリンピック　春季トレーニング合宿](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)。