24925번 - Clumsy Cardinals 다국어

Everyone knows that in the game chess, a bishop moves diagonally. Boring! Consider a new piece called a cardinal. A cardinal moves diagonally, like a bishop but they are clumsy. If its movement brings a cardinal adjacent to another piece, it trips and falls on the other piece. This results in the other piece being captured and removed from the board. The cardinal that was moving then rests on the captured piece’s square. Note two squares are adjacent if they share a side, meaning they are directly horizontal or vertical from one another. A cardinal can also capture pieces like a bishop if the other piece lies on the same diagonal. A cardinal can only move if the movement results in the capture of another piece.

In this problem, you are given the initial locations of cardinal pieces on an infinite chessboard. Determine the minimum number of cardinals that remain on the board under some sequence of valid moves.

The first line of input contains a single integer $N$ ($1≤N≤10^5$), which is the number of cardinal pieces to consider.

The next line contains $2N$ space-separated integers $r_1,c_1,r_2,c_2,\dots ,r_N,c_N$ ($10^{-9}≤r_i,c_i≤10^9$). These give the initial cardinal locations, so cardinal $i$ initially lies on square $(r_i,c_i)$. Furthermore, $|r_i-r_j|≥2$ or $|c_i-c_j|≥2$ (or both) for any $1≤i<j≤N$.

Display the minimum number of cardinals that remain on the board though some sequence of valid moves.