P1849 [USACO12MAR] Tractor S

After a long day of work, Farmer John completely forgot that his tractor was still in the middle of the field. His cows, who love to play pranks on him, dropped $n$ hay bales at various positions in the field. This means John must move some hay bales out of the way before he can drive the tractor out. Both the tractor and the hay bales are treated as points on a two-dimensional plane with integer coordinates. No hay bale shares the same coordinates as the tractor’s initial position. John can drive the tractor only along the coordinate axes for some number of units. For example, he can first move north by $2$ units and then east by $3$ units, and so on. The tractor cannot move onto a point occupied by a hay bale. Please help John compute the minimum number of hay bales that must be moved so that he can drive the tractor back to the origin.

The first line contains three space-separated integers, giving the number of hay bales $n$ and the tractor’s starting coordinates $(x_0, y_0)$. Lines $2$ through $(n+1)$: each line contains two space-separated integers. On line $(i + 1)$, the integers $x_i, y_i$ give the coordinates of the $i$-th hay bale $(x_i, y_i)$.

Output a single integer on one line: the minimum number of hay bales that must be moved so John can drive the tractor back to the origin.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^4$, $1 \leq x_i, y_i \leq 10^3$. Translated by ChatGPT 5