#5060. 「POI2017 R2」城堡 Castle

传统 250 - 19000 ms 256 MiB

题目描述

题目译自 XXIV Olimpiada Informatyczna — II etap Zamek

一群寻宝者得到了一份城堡地牢的地图，地图标注了隐藏的宝藏位置。地图基于方格网格，网格点坐标为整数，左下角为 $(0,0)$，右上角为 $(w, h)$。地牢分为 $n$ 个房间，每间房间为矩形，边沿网格线，房间内部互不重叠，完整覆盖地牢区域。两房间间若对应矩形边相邻（仅顶点相接不足以连通），则存在直接通道。

寻宝者位于地图某点，宝藏位于另一点。需计算寻宝者最少经过多少房间，从起始点到达宝藏。难点在于，部分房间可能含有危险区域，为安全起见，寻宝者应避免进入此类房间。

输入格式

第一行包含四个整数 $w$, $h$, $n$, $m$ ($w, h \geq 2$, $n \geq 1$, $m \geq 0$)，分别表示地图宽度、高度、房间数量和危险区域数量。

第二行包含两个整数 $x_P$, $y_P$，表示寻宝者的起始坐标。

第三行包含两个整数 $x_S$, $y_S$，表示宝藏的坐标。

接下来的 $n$ 行描述房间，第 $i$ 行包含四个整数 $x_1$, $y_1$, $x_2$, $y_2$，表示第 $i$ 个房间为对角顶点为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的矩形。

接下来的 $m$ 行描述危险区域，第 $i$ 行包含两个整数 $x$, $y$，表示第 $i$ 个危险区域的坐标。

保证寻宝者和宝藏所在房间无危险区域，所有坐标满足 $0 \leq x \leq w$, $0 \leq y \leq h$，且寻宝者、宝藏和危险区域均位于某房间内部。

输出格式

输出一行，包含一个整数，表示寻宝者从 $(x_P, y_P)$ 到 $(x_S, y_S)$ 最少需经过的房间数量，且不进入含危险区域的房间。寻宝路径无需沿网格线（见图示）。保证存在至少一条合法路径。

样例

输入

7 6 9 3
1 1
6 4
0 0 3 2
3 1 6 3
3 0 5 1
5 0 7 1
6 1 7 3
0 2 3 6
3 3 5 5
3 5 5 6
5 3 7 6
4 2
5 2
4 4

输出

4

数据范围与提示

令 $W=1000000000$, $N=1000000$。

详细子任务附加限制及分值如下表所示。