P6200 [USACO07OCT] Super Paintball G

The cows recently bought a set of simulated paintball game equipment from a toy dealer (similar to real-life CS). Bessie divided the lawn where they play into an $N \times N$ grid ($1 \leq N \leq 100$), and she also figured out the positions of her $K$ opponents on the lawn ($1 \leq K \leq 10^5$). Now you need to help Bessie compute something. In this game, the cows can fire in any one of eight directions: due north, due south, due east, due west, northeast, southeast, northwest, and southwest (northeast means $45^\circ$ east of north; the same applies to southeast, northwest, and southwest). Bessie wants you to calculate how many positions allow her to shoot all opponents. In particular, Bessie may stand on the same cell as one of her opponents; in that case, she can shoot the opponent in the same cell.

The first line contains two integers $N, K$. The next $K$ lines each contain two integers $R_i, C_i$, meaning the $i$-th cow is at row $R_i$ and column $C_i$. It is possible for two cows to be at the same position.

Output the number of cells Bessie can choose.

The possible positions are: $(2,1),(2,3),(3,2),(4,1),(4,3)$. Translated by ChatGPT 5