Unique GPS Positioning via Expanding Spiral

A new-age GPS company claims that a traditional map is almost useless if you don’t know exactly where you are – but a GPS tells you instantly. In this problem, you are given the complete map of a test area: a flat, unbounded Cartesian grid where only a finite number of cells contain a marker. You are placed at an unknown grid cell and you start exploring your surroundings by following an expanding clockwise spiral.

The spiral path starts at cell (0,0) (the starting cell) and then proceeds as follows:

Step 0: (0,0)
Then, for layer L ≥ 1, the spiral visits the 8L cells on the boundary of the square of side length 2L+1 in the following order:
  • Segment 1 (moving downward along the right side): for i = 0 to 2L-1, cell = (L, (L-1) - i).
  • Segment 2 (moving leftward along the bottom): for i = 0 to 2L-1, cell = (L-1 - i, -L).
  • Segment 3 (moving upward along the left side): for i = 0 to 2L-1, cell = (-L, -L+1 + i).
  • Segment 4 (moving rightward along the top): for i = 0 to 2L-1, cell = (-L+1 + i, L).

Your task is to simulate a test subject who, starting at an unknown grid cell p (in the absolute coordinate system), uses this spiral exploration. At each step the subject sees whether the current cell contains a marker (all empty cells look identical and all marked cells look identical). The subject stops exploring as soon as the observed sequence of markers (or emptiness) could only have been produced if the starting cell were p.

A key observation is that, because the grid contains only finitely many markers, the test subject will definitely see all markers after a finite number of steps. In fact, once every marker has been visited by the spiral, the complete configuration of markers (translated by –p) is revealed and p is uniquely determined.

Thus, if we denote by f(dx,dy) the index (starting from 0) at which the spiral first visits the relative cell (dx,dy) and if a marker is at absolute position m then its relative coordinate is (m_x − p_x, m_y − p_y), the minimal number of steps required is

$$T = 1 + \max_{m \in M} \{ f(m_x-p_x,\,m_y-p_y) \}. $$

Given the starting cell p and the positions of all markers, compute T.

inputFormat

The first line contains two space‐separated integers px and py denoting the coordinates of the starting cell.

The second line contains a single integer n (n ≥ 1) representing the number of markers.

Each of the next n lines contains two space‐separated integers x and y which denote the coordinates of a marker. It is guaranteed that all marker positions are distinct.

outputFormat

Output a single integer T – the minimum number of steps needed along the spiral that ensures all markers have been observed, and hence your starting position is uniquely determined.

sample

0 0
5
1 0
1 -1
0 -1
-1 0
-1 1

7