UCLA ICPC | Winter Practice #1


2022-01-16 13:20 AKST

UCLA ICPC | Winter Practice #1


2022-01-16 18:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -123 days 9:47:31

Time elapsed


Time remaining


Problem N
God Save the i-th Queen

Did you know that during the ACM-ICPC World Finals a big chessboard is installed every year and is available for the participants to play against each other? In this problem, we will test your basic chess-playing abilities to verify that you would not make a fool of yourself if you advance to the World Finals. Let us centrate on queens. As you probably know, the queens may move not only horizontally and vertically, but also diagonally. You are given a chessboard with $i-1$ queens already placed and your task is to find all squares that may be used to place the $i$-th queen such that it cannot be captured by any of the others.


The input consists of several tasks, at most $5$. Each task begins with a line containing three integer numbers separated by a space: $X, Y, N$. $X$ and $Y$ give the chessboard size, $1\leq X, Y \leq 20\, 000$. $N = i-1$ is the number of queens already placed, $0\leq N\leq \min (X\cdot Y, 20\, 000)$. After the first line, there are $N$ lines, each containing two numbers $x_ k, y_ k$ separated by a space. They give the position of the $k$-th queen, $1\leq x_ k \leq X, 1\leq y_ k\leq Y$. You may assume that those positions are distinct, i.e., no two queens share the same square. The last task is followed by a line containing three zeros.


For each task, output one line containing a single integer number: the number of squares which are not occupied and do not lie on the same row, column, or diagonal as any of the existing queens.

Sample Input 1 Sample Output 1
8 8 2
4 5
5 5
0 0 0