题目描述
译自 JOI Open 2017 T3 「ゴルフ / Golf」
平面的第一象限上有 N 个矩形障碍,矩形的两组对边分别平行于 x 轴和 y 轴。矩形 i(1≤i≤N) 的左下角是 (Ai,Ci),右上角是 (Bi,Di)。任意两个矩形(包括边界)不相交。
JOI 君需要将一个高尔夫球从 (S,T) 打到 (U,V),保证这两点不同,保证这两点不在障碍内或障碍的边界上。
JOI 君只能朝平行于 x 轴或平行与 y 轴的方向击球(JOI 君可以跟着移动)。球可以经过边界,但不能进入障碍物内部。球撞进障碍物后会停下(JOI 君仍然可以朝远离障碍物的方向击球)。
求最少要击球多少次,才能将高尔夫球打进 (U,V)。
输入格式
第一行有四个整数 S,T,U,V。
第二行有一个整数 N。
在接下来的 N 行中,每行有四个整数 Ai,Bi,Ci,Di。
输出格式
输出一行,一个整数,表示最少击球次数。
提示
样例解释 1
(3,5)→(3,2)→(8,2)→(8,6)
数据范围
1≤S,T,U,V≤109,1≤N≤105,1≤Ai<Bi≤109,1≤Ci<Di≤109, (S,T)=(U,V)。
- 子任务 #1(10 分):S,T,U,V,N,Bi,Di≤1000;
- 子任务 #2(20 分):N≤1000;
- 子任务 #3(70 分):没有额外限制。