Cows on Ice

Bessie is ice skating on a large frozen lake modeled as a 2D grid whose coordinates range from $-10^9$ to $10^9$ on both axes. $N$ ($1 \le N \le 20000$) of the grid cells contain rocks, numbered $1$ through $N$; every other cell is slippery ice.

Bessie is a poor skater, so she can only move by pushing off from her current cell (which always sits next to a rock) and then sliding in a straight line until she slams into another rock, coming to rest in the cell immediately before that rock. She can push herself only straight north, east, south, or west, and she cannot push through a rock, so she usually has at most three useful directions.

A slide only works if some rock lies ahead of her in that direction to stop her; with no rock ahead she would slide forever, so every push must be aimed carefully.

For example, Bessie (B) wants to reach the goal (G) at $(x = 5, y = 1)$, directly east of her (. = ice, * = rock, B = Bessie, G = goal). Sliding straight east would carry her past the goal, because she can only stop by hitting a rock. One way to reach $(5, 1)$ is:

   (a)              (b)             (c)              (d)
4 .....*.         .....*.         .....*.          .....*.
3 ..*....  slide  ..*....  slide  ..*....   slide  ..*....
2 ......*  north  ..B...*  east   .....B*   south  ......*
1 .*B..G. ------> .*...G. ------> .*...G.  ------> .*...B.
0 *....*.         *....*.         *....*.          *....*.
  0123456

In situation (a) she could try north, east, or south, but only the northward slide has a rock to stop her. In situation (b) only the eastward slide has a stopping rock.

Rock $i$ sits at $(X_i, Y_i)$ with each coordinate between $-10^9$ and $10^9$, and no two rocks share a cell. Bessie starts at $(B_x, B_y)$, always next to a rock, and her goal is $(G_x, G_y)$; every coordinate lies in the same range, and the goal is always reachable.

Sliding costs Bessie nothing, but pushing off a rock tires her out. Determine the minimum number of pushes she needs to reach the goal.

• Line 1: five space-separated integers $N$, $B_x$, $B_y$, $G_x$, $G_y$.
• Lines 2 through $N + 1$: line $i + 1$ contains two space-separated integers $X_i$ and $Y_i$, the location of rock $i$.

• Line 1: a single integer, the minimum number of pushes Bessie needs to reach her goal.