P7559 [JOISC 2021] IOI Fever Infection Spread (Day1)

In the JOI Kingdom, there are $N$ palaces. The $i$-th palace is located at $(X_i, Y_i)$. Each palace is home to one prince; the prince in the $i$-th palace is Prince $i$. Starting from time $0$, every prince will leave their own palace and start moving. They can choose one of the four directions: east, south, west, or north. - If they choose east, then after time $t$, their position changes from $(x, y)$ to $(x + t, y)$. - If they choose west, then after time $t$, their position changes from $(x, y)$ to $(x - t, y)$. - If they choose south, then after time $t$, their position changes from $(x, y)$ to $(x, y - t)$. - If they choose north, then after time $t$, their position changes from $(x, y)$ to $(x, y + t)$. $t$ does not have to be an integer. The directions will not be given; you can plan them yourself. Unfortunately, Prince $1$ has been infected with the IOVID-114514 virus, and at time $0$, only Prince $1$ is infected. The IOVID-114514 virus spreads in the following way: - If at some time, Prince $a$ and Prince $b$ are at the same coordinate, and Prince $a$ is infected while Prince $b$ is not, then Prince $a$ will infect Prince $b$. The IOVID-114514 virus has no other way of spreading, and the poor King JOI 114514 has not found any cure. (Disinfectant cannot cure it either.) King JOI 114514 wants you to find the maximum number of princes that can be infected by time $10^{100}$.

The first line contains an integer $N$, representing the number of palaces. The next $N$ lines each contain two integers $X_i, Y_i$, representing the coordinates of a palace.

Output one integer on a single line, representing the answer.

#### Explanation of Sample 1  We plan Prince $1$ to move east, and Prince $2$ to move west. It is not hard to see that no matter how they move, Prince $1$ can never meet Prince $2$, so only Prince $1$ is infected. #### Explanation of Sample 2  We plan Prince $1$ to move east, Prince $2$ to move north, and Prince $3$ to move west. - At time $0$, Prince $1$ is infected. - At time $1$, Prince $1$ and Prince $2$ are at the same coordinate, so Prince $2$ becomes infected. - At time $2$, Prince $2$ and Prince $3$ are at the same coordinate, so Prince $3$ becomes infected. #### Explanation of Sample 3 We plan Prince $1$ to move north, and Prince $2$ to move south. - At time $0$, Prince $1$ is infected. - At time $0.5$, Prince $1$ and Prince $2$ are at the same coordinate, so Prince $2$ becomes infected. #### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (5 pts): $N \le 7$, satisfies Property A. - Subtask 2 (8 pts): $N \le 15$, satisfies Property A. - Subtask 3 (6 pts): $N \le 100$, satisfies Properties A and B. - Subtask 4 (6 pts): $N \le 100$, satisfies Property A. - Subtask 5 (12 pts): $N \le 3000$. - Subtask 6 (32 pts): satisfies Property A. - Subtask 7 (31 pts): no special restrictions. For $100\%$ of the testdata: $1 \le N \le 10^5$, $0 \le X_i, Y_i \le 5 \times 10^8$, and all palace coordinates are distinct. The properties are: - Property A: $X_i \ne X_j$, $Y_i \ne Y_j$. - Property B: the coordinate of Palace $1$ is the origin. #### Notes Translated from [The 20th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html), [Day1 B IOI 熱の感染拡大 (IOI Fever) English version](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/fever-en.pdf). Translated by ChatGPT 5