[JOI Open 2017] 高尔夫 / Golf

Luogu

IDLGP10631

Time5000ms

Memory1024MB

DifficultyP6

2017线段树广度优先搜索 BFS扫描线JOI（日本）

**译自 [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)$。任意两个矩形（包括边界）不相交。 JOI 君需要将一个高尔夫球从 $(S,T)$ 打到 $(U,V)$，保证这两点不同，保证这两点不在障碍内或障碍的边界上。 JOI 君只能朝平行于 $x$ 轴或平行与 $y$ 轴的方向击球（JOI 君可以跟着移动）。球可以经过边界，但不能进入障碍物内部。球撞进障碍物后会停下（JOI 君仍然可以朝远离障碍物的方向击球）。求最少要击球多少次，才能将高尔夫球打进 $(U,V)$。 ## Input 第一行有四个整数 $S, T, U, V$。第二行有一个整数 $N$。在接下来的 $N$ 行中，每行有四个整数 $A_i, B_i, C_i, D_i$。 ## Output 输出一行，一个整数，表示最少击球次数。 [samples] ## Note **样例解释 1** $(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)$。 - 子任务 #1（10 分）：$S, T, U, V, N, B_i, D_i\le 1000$； - 子任务 #2（20 分）：$N\le 1000$； - 子任务 #3（70 分）：没有额外限制。

Samples

Input #1

3 5 8 6
1
5 6 2 8

Output #1

Input #2

Output #2

Input #3

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

Output #3

API Response (JSON)

{
  "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)$。任意两个矩形（...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments