P2981 [USACO10FEB] Cows on Ice G

题目描述

Bessie在二维平面表示的冰封湖面上滑冰，坐标范围为 -10^9 到 10^9。

湖面有 $N$ 个石块（编号 1 到 $N$），其他位置为冰面。

Bessie通过推动相邻石块的反作用力向 东、南、西、北 四个方向滑行，在碰到新石块前不会停止（最终停留在目标石块的前一格）。

Bessie无法穿越石块，因此每次最多只能朝三个方向滑行，且必须能碰到石块才能停止。

目标是从起点 $(B_x, B_y)$（与某个石块相邻）到达终点 $(G_x, G_y)$，求最少需要推动石块的次数。

输入格式

• 第一行五个整数 $N ，B_x, B_y, G_x, G_y$。
• 接下来 $N$ 行，每行两个整数 $X_i, Y_i$，表示第 $i$ 个石块的位置。

$1 \le N \le 20000$

$-10^9 \le B_x,B_y,G_x,G_y,X_i,Y_i \le 10^9$

输出格式

• 输出一个整数表示最少推动次数。

输入输出样例 #1

输入 #1

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

输出 #1

3