解题思路

1. 模型转换 将平面连续格网离散化，只关心所有矩形边界以及起、终点的横纵坐标。

2. 坐标压缩与节点构造

   • 收集所有矩形的 $X_{1,i},X_{2,i}$ 以及起点、终点的 $x$ 坐标，共计 $M_x$ 个不同值；同理收集所有 $Y_{1,i},Y_{2,i}$ 及起终点的 $y$ 坐标，共计 $M_y$。
   • 构造所有可能的“重要”交叉点 $P=(x_j,y_k)$，其中 $x_j$ 取自上述压缩后横坐标集合，$y_k$ 取自纵坐标集合。

题目内容

小钉生活在未来超级城市，未来超级城市是一个矩形街道网格。每个交叉点具有整数笛卡尔坐标 $x$ 和 $y$ 。从交叉点 $a$ (坐标 $xa,ya$ )到交叉点 $b$ (坐标北 $xb,yb$ )，你需要驾驶恰好 $|xa-xb| +|ya-yb|$ 个街区。通常情况下，驾驶通过一个街区需要 $10$ 个时间单位，因此可以轻松计算从 $a$ 到 $b$ 所需的时间。然而，超级城市中通过交通拥堵使区域得最小行驶时间的估算变得复杂，需要你解决这个问题。

交通拥堵影响一个由左下角和右上角坐标定义的矩形区域。在该拥堵区域中，驾驶一个街区所需的时间由给定的拥堵时间决定。所有严格位于矩形区域内部的街道都会受到交通拥堵的影响。有时，绕开交通拥堵区域可以节省时间，而省时，如示例所示，穿过部分拥堵区域可能更优——例如，$17$ 个街区在非拥堵区域行驶(每个街区耗时 $10$ 个时间单位,大计需要 $170$ 时间单位)，而 $2$ 个街区在轻度拥堵区域行驶(每个街区耗时 $11$ 个时间单位，共计需要 $22$ 时间单位)。