暴力是直接求出 $O(n^2)$ 个交点之后跑最短路，时间复杂度 $O(n^2\log n)$。

注意到像完全的网格之类的情况是可以优化的。我们考虑减少关键点的数量。

先把坐标离散化，假设值域是 $O(n)$。按照 $\sqrt n$ 的大小把横坐标分块，为了方便，我们把起点终点也当作块端点。块端点一整列都作为关键点，这部分是 $O(n\sqrt n)$。每条水平线段要么和块不相交，要么包含，要么端点在块中。我们把端点在块中的块内的一整行都作为关键点，因为端点数是 $O(n)$，每个端点 $O(\sqrt n)$，所以这部分也是 $O(n\sqrt n)$。

现在还剩下一种情况：一个矩形所有边界都是关键点，并且每一行都是从左到右完整的线段。在这种情况下，只需要把每条竖直方向的线段的最上和最下的两个交点，以及交点左右最近的其他竖直线段的交点作为关键点即可。同样每个块端点也只需要走到最近的竖直线段。这里可以用 set 维护，从左往右和从右往左都扫一遍就能求出关键点。每条竖直线段最多只会贡献 $O(1)$ 个关键点，再加上每一块端点会贡献 $O(n)$ 个关键点，所以也是 $O(n\sqrt n)$ 的。

求出所有关键点之后，连边，跑 Dijkstra，总时间复杂度 $O(n\sqrt n\log n)$。