P15637 [2019 KAIST RUN Spring] Dijkstra Is Playing At My House

为了庆祝你的队伍在 ICPC 世界总决赛中获胜，Edsger W. Dijkstra（Dijkstra 算法的发明者和命名者）将在你位于纽约市的家中举办一场盛大的派对。派对将在 5 小时后开始，所以他最好现在就动身。 纽约市被建模为一个二维平面。Dijkstra 当前位于坐标 $(s_x, s_y)$，而你的家位于坐标 $(e_x, e_y)$。Dijkstra 只能沿着与坐标轴平行的方向移动（你还记得**曼哈顿距离**，对吧？）。此外，有 $N$ 座摩天大楼，它们都是与坐标轴平行的矩形，你可以穿过其边界，但不能穿过其严格内部（即矩形内部）的任何地方。 你接到了 Dijkstra 的电话，他说计算从他所在位置到你家的最短路径对他来说太难了。不知为何，他正在失去他的优势。然而，这并非坏消息，因为这是你在伟大的 Dijkstra 面前展现风采的机会。你能做到吗？ 保证所有 $x$ 坐标互不相同，所有 $y$ 坐标也互不相同。同时保证任意两个矩形不重叠。还保证你的家和 Dijkstra 的起始位置都不在任何矩形内部。

第一行包含五个整数 $N, s_x, s_y, e_x, e_y$。 ($1 \le N \le 250 000, 0 \le s_x, s_y, e_x, e_y \le 10^8$) 接下来的 $N$ 行，每行包含四个整数 $a_i, b_i, c_i, d_i$。这表示第 $i$ 座摩天大楼是一个矩形，其四个角位于 $(a_i, b_i), (a_i, d_i), (c_i, b_i), (c_i, d_i)$。 ($0 \le a_i < c_i \le 10^8$, $0 \le b_i < d_i \le 10^8$) **保证以下条件：** - 令 $X = \{s_x, e_x, a_1, a_2, \cdots, a_N, c_1, c_2, \cdots, c_N\}$, $Y = \{s_y, e_y, b_1, b_2, \cdots, b_N, d_1, d_2, \cdots, d_N\}$。$X$ 中的所有元素互不相同，$Y$ 中的所有元素也互不相同。 - 任意两个矩形没有公共点。 - Dijkstra 的位置和你家的位置都不在任何矩形内部。

输出 Dijkstra 的位置到你的家之间，使用曼哈顿度量的最短路径长度。

翻译由 DeepSeek 完成