1504. The Ring That Holds a Cell
An R by C grid has its boundary layers numbered from 0 outwards in, exactly
as in problem 1501. The grid itself is never given.
For each of q cells, given by its 1-based row r and column c, print two
numbers: the index of the ring the cell lies on, and how many cells that whole
ring holds.
R = 4, C = 5 (1,1) -> 0 14 (2,2) -> 1 6
(2,3) -> 1 6 (4,5) -> 0 14
R = 1, C = 7 (1,4) -> 0 7 ring 0 is the entire row, seven cells
R = 5, C = 5 (3,3) -> 2 1 the centre cell is a ring of its own
## What most people try first
Peeling the grid: build an R by C array, mark ring 0, remove it, mark ring
1, and so on. It is correct and it costs O(R C) memory. With R and C at
10^9 that is 10^18 cells, so the grid cannot exist.
The second reflex is the ring SIZE formula 2 (h + w) - 4, where
h = R - 2t and w = C - 2t. On a 1 by 7 grid that gives
2 (1 + 7) - 4 = 12 for a ring that holds 7 cells. A square grid never
produces a ring one cell thick in only one direction, so this passes every
square test and fails the first rectangle.
## The ring index is a distance to the nearest edge
A cell is on ring t exactly when t steps inward from the nearest edge reach
it, so
t = min(r - 1, c - 1, R - r, C - c) with r and c 1-based
and the size of ring t, with h = R - 2t and w = C - 2t, is
w if h == 1 the ring is a single row
h if w == 1 the ring is a single column
2 * (h + w) - 4 otherwise
## Why the min is the right definition
Peeling one ring removes the first row, the last row, the first column and the
last column. A cell survives t peels exactly when it is at least t away
from all four of those, and it dies on peel number min of the four
distances. Nothing about the shape enters the argument, so it holds for any
R and C.
## Why the general size formula double counts
2 (h + w) - 4 counts the top row, the bottom row, the left column and the
right column, then removes the four corners once each. When h == 1 the top
row and the bottom row are the SAME w cells, and the four corners are only
two distinct cells, so the correction is wrong twice over.
## Overflow
With R = C = 10^9, ring 0 holds 2 (10^9 + 10^9) - 4 = 3999999996 cells.
That is past the 2147483647 a signed 32 bit integer holds, so the SIZE needs
64 bits even though R, C and the ring index each fit comfortably in 32.
## Cost
O(1) per query and O(1) memory. Problem 1503 asks the opposite question,
from a spiral position to a cell, and needs a binary search to get there; this
direction needs none.
Constraints - `1 ≤ R ≤ 10^9` - `1 ≤ C ≤ 10^9` - `1 ≤ q ≤ 200000` - `1 ≤ r ≤ R` and `1 ≤ c ≤ C` - `R` and `C` are independent; the grid need not be square
Input
The first line contains three integers R, C and q.
Each of the next q lines contains two integers r and c, both 1-based.
Output
Print q lines, one per query in arrival order. Each line holds two integers separated by a single space: the 0-based ring index of that cell, then the total number of cells on that ring.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.