#P10631. [JOI Open 2017] 高尔夫

[JOI Open 2017] 高尔夫

题目描述

译自 JOI Open 2017 T3 「ゴルフ / Golf」

平面的第一象限上有 NN 个矩形障碍,矩形的两组对边分别平行于 xx 轴和 yy 轴。矩形 i(1iN)i(1\le i\le N) 的左下角是 (Ai,Ci)(A_i, C_i),右上角是 (Bi,Di)(B_i, D_i)。任意两个矩形(包括边界)不相交。
JOI 君需要将一个高尔夫球从 (S,T)(S,T) 打到 (U,V)(U,V),保证这两点不同,保证这两点不在障碍内或障碍的边界上。
JOI 君只能朝平行于 xx 轴或平行与 yy 轴的方向击球(JOI 君可以跟着移动)。球可以经过边界,但不能进入障碍物内部。球撞进障碍物后会停下(JOI 君仍然可以朝远离障碍物的方向击球)。
求最少要击球多少次,才能将高尔夫球打进 (U,V)(U,V)

输入格式

第一行有四个整数 S,T,U,VS, T, U, V
第二行有一个整数 NN
在接下来的 NN 行中,每行有四个整数 Ai,Bi,Ci,DiA_i, B_i, C_i, D_i

输出格式

输出一行,一个整数,表示最少击球次数。

3 5 8 6
1
5 6 2 8
3
1 1 1 10
3
5 6 2 8
1 2 2 3
8 10 3 5
1
20 68 85 74
5
30 70 14 100
5 24 15 67
75 86 75 79
75 90 19 62
93 98 26 58
4

提示

样例解释 1

(3,5)(3,2)(8,2)(8,6)(3,5) → (3,2) → (8,2) → (8,6)

数据范围

$1\le S, T, U, V\le 10^9, 1\le N\le 10^5, 1\le A_i<B_i\le 10^9, 1\le C_i<D_i\le 10^9,$ (S,T)(U,V)(S,T)≠(U,V)

  • 子任务 #1(10 分):S,T,U,V,N,Bi,Di1000S, T, U, V, N, B_i, D_i\le 1000
  • 子任务 #2(20 分):N1000N\le 1000
  • 子任务 #3(70 分):没有额外限制。