Upon closer inspection, the task asks to count, among all cells at most ~K~ steps from the origin, the number of cells with even distance and the number of cells with odd distance. One might say that we're colouring the cells with two colours.

The colour of a cell is uniquely determined by its coordinates, since each step changes the parity of the expression ~x+y~. Because of this, two adjacent cells are necessarily coloured differently. Additionally, the distances of two adjacent cells differ by exactly ~1~.

The image shows the second sample test, with a slightly larger number of steps ~S~. Observe the smallest rectangle surrounding all obstacles and the origin, and expand it one cell in all four directions:

The absolute values of the obstacles' coordinates are at most ~1000~ so the distances of all cells inside the rectangle can be found with breadth-first search.

For example, consider a cell is on the left edge of the rectangle (but inside it), distance some ~D~ steps from the origin. Then exactly ~K-D~ cells to its left (outside the rectangle) will be coloured, and simple formulas will give the number of cells of one and the other colour in ~\mathcal O(1)~. We proceed identically for cells on the other three edges of the rectangle.

We still need to count the cells off the corners; for example, the cells above and to the left of the yellow cell in the upper-left corner of the rectangle. A triangular pattern is obvious and there are formulas (see sample code) for this case too. But since ~S~ is on the order of millions, doing it in ~\mathcal O(S)~ for each corner instead of ~\mathcal O(1)~ will do, too.