[USACO10FEB] Cows on Ice G

Bessie is ice skating on a large frozen lake modelled as a 2-dimensional grid with coordinates in the range -1,000,000,000..1,000,000,000. N (1 <= N <= 20,000) of the lake's grid cells contain rocks (conveniently numbered 1..N). The other cells contain slippery ice. Since Bessie is not a very good skater, she traverses the lake's cells by pushing herself away from her current position near a rock and sliding continuously in the same direction until she hits another rock (stopping in the square before she hits the rock, of course). Never good with complicated angles, Bessie can push herself only straight north, east, south, or west. She can't push herself through the rock, of course, and thus generally has only three possible directions to move. Sliding is not without risks. Bessie must hit a rock or might end up sliding for a very long time. She must aim her pushes carefully. Consider the situation depicted below; Bessie wants to get to location (x=5,y=1), which is east of her current location (. = ice, \* = rock, B = Bessie, G = goal). If she slides directly to the east, she will slide past the location since she can stop only by encountering a rock head on. One way to get to (5,1) is the following: (a) (b) (c) (d) 4 .....\*. .....\*. .....\*. .....\*. 3 ..\*.... slide ..\*.... slide ..\*.... slide ..\*.... 2 ......\* north ..B...\* east .....B\* south ......\* 1 .\*B..G. ------> .\*...G. ------> .\*...G. ------> .\*...B. 0 \*....\*. \*....\*. \*....\*. \*....\*. 0123456 Bessie could slide north, east, or south in situation (a), but only north has a rock for stopping. For situation (b), she can slide only east for the same reason. For the input, rock i is located at cell X\_i,Y\_i (-1,000,000,000 <= X\_i <= 1,000,000,000; -1,000,000,000 <= Y\_i <= 1,000,000,000), and no two rocks occupy the same position. Bessie starts at Bx,By (which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000; -1,000,000,000 <= By <= 1,000,000,000). Bessie's goal is Gx,Gy (-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <= 1,000,000,000). Bessie can always reach the goal one way or another. Bessie doesn't mind sliding. However, pushing herself away from a rock is very tiring. To prepare her, FJ would like to know the minimum number of pushes Bessie needs to do. Bessie 在一个冰封的湖面上游泳，湖面可以表示为二维的平面，坐标范围是-1,000,000,000..1,000,000,000。湖面上的N(1 <= N <= 20,000)个位置有石块(编号分别为1到N)，其它位置是冰面。由于Bessie滑冰技术不够好，她通过推动自己旁边的石块，依靠反作用力向某一个方向前进，在碰到一个新的石块之前，Bessie是不会停下来的。(当然，最后会停留在某块石块的前一个格子里)由于Bessie无法计算复杂的角度，她只能够向东南西北四个方向前进。 很显然，Bessie不能够穿越石块，因此，Bessie仅仅可以向三个方向滑。 滑冰不是没有风险，Bessie滑向某个方向后必须能碰到某个石块，因此她必须很小心。考虑下面的一个情况，Bessie希望到达在她东面的目标位置(x=5,y=1)，(…

\* Line 1: Five space separated integers: N, Bx, By, Gx, and Gy \* Lines 2..N+1: Line i+1 describes a rock location with space separated integers: X\_i and Y\_i

\* Line 1: A single integer that is the minimum number of pushes for Bessie to get to her goal

6 2 1 5 1 
5 4 
2 3 
1 1 
6 2 
5 0 
0 0 

3