{"problem":{"name":"[JOI Open 2017] 高尔夫 / Golf","description":{"content":"**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T3 「ゴルフ / Golf」** 平面的第一象限上有 $N$ 个矩形障碍，矩形的两组对边分别平行于 $x$ 轴和 $y$ 轴。矩形 $i(1\\le i\\le N)$ 的左下角是 $(A_i, C_i)$，右上角是 $(B_i, D_i)$。任意两个矩形（","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10631"},"statements":[{"statement_type":"Markdown","content":"**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T3 「ゴルフ / Golf」**\n\n平面的第一象限上有 $N$ 个矩形障碍，矩形的两组对边分别平行于 $x$ 轴和 $y$ 轴。矩形 $i(1\\le i\\le N)$ 的左下角是 $(A_i, C_i)$，右上角是 $(B_i, D_i)$。任意两个矩形（包括边界）不相交。  \nJOI 君需要将一个高尔夫球从 $(S,T)$ 打到 $(U,V)$，保证这两点不同，保证这两点不在障碍内或障碍的边界上。  \nJOI 君只能朝平行于 $x$ 轴或平行与 $y$ 轴的方向击球（JOI 君可以跟着移动）。球可以经过边界，但不能进入障碍物内部。球撞进障碍物后会停下（JOI 君仍然可以朝远离障碍物的方向击球）。  \n求最少要击球多少次，才能将高尔夫球打进 $(U,V)$。\n\n## Input\n\n第一行有四个整数 $S, T, U, V$。  \n第二行有一个整数 $N$。  \n在接下来的 $N$ 行中，每行有四个整数 $A_i, B_i, C_i, D_i$。\n\n## Output\n\n输出一行，一个整数，表示最少击球次数。\n\n[samples]\n\n## Note\n\n**样例解释 1**\n\n$(3,5) → (3,2) → (8,2) → (8,6)$\n\n#### 数据范围\n\n$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)$。  \n\n- 子任务 #1（10 分）：$S, T, U, V, N, B_i, D_i\\le 1000$；  \n- 子任务 #2（20 分）：$N\\le 1000$；  \n- 子任务 #3（70 分）：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10631","tags":["2017","线段树","广度优先搜索 BFS","扫描线","JOI（日本）"],"sample_group":[["3 5 8 6\n1\n5 6 2 8","3"],["1 1 1 10\n3\n5 6 2 8\n1 2 2 3\n8 10 3 5","1"],["20 68 85 74\n5\n30 70 14 100\n5 24 15 67\n75 86 75 79\n75 90 19 62\n93 98 26 58","4"]],"created_at":"2026-03-03 11:09:25"}}