[AdditionalFile6994.zip](file://AdditionalFile6994.zip?type=additional_file)

#6994. 「ICPC World Finals 2025」阳光下行走

标签: 传统 | 时间限制: 2000 ms | 内存限制: 2048 MiB |

题目描述

我走在阳光下，感觉不太好——我的眼睛好痛！

巴库阳光充足。如果你背对太阳行走，或者至少垂直于太阳光线行走，阳光就不会刺到你的眼睛。在这个问题中，假设太阳从南方照射。向西、向东或任何介于东西之间且带有向北分量的方向行走，都可以避免直视太阳。如果你向任何带有向南分量的方向行走，你的眼睛就会感到刺痛。

巴库也有许多矩形的阴影区域，待在这些区域里可以保护你的眼睛，无论你朝哪个方向行走。例如，图 L.1 展示了两个阴影区域。

请找出从比赛地点到颁奖典礼地点，你需要在阳光刺眼的情况下行走的最短距离。

图 L.1：样例输入 1 以及一条使阳光刺眼距离最小化的路径。 ## 输入格式

输入的第一行包含五个整数 $n, x_{c}, y_{c}, x_{a}$ 和 $y_{a}$，其中 $n$ $(0 \leq n \leq 10^{5})$ 是阴影区域的数量，$(x_{c}, y_{c})$ 是比赛地点的位置，而 $(x_{a}, y_{a})$ $(-10^{6} \leq x_{c}, y_{c}, x_{a}, y_{a} \leq 10^{6})$ 是颁奖典礼地点的位置。太阳从南向北照射，方向为 $(0, 1)$。如果你行走的方向为 $(x, y)$，其中 $y<0$ 且 $x$ 为任意值，那么你就会直视太阳。

接下来的 $n$ 行描述了阴影区域，它们是与坐标轴对齐的矩形。这些行中的每一行都包含四个整数 $x_{1}, y_{1}, x_{2}$ 和 $y_{2}$ $(-10^{6} \leq x_{1}<x_{2} \leq 10^{6} ;-10^{6} \leq y_{1}<y_{2} \leq 10^{6})$。矩形的西南角是 $(x_{1}, y_{1})$，东北角是 $(x_{2}, y_{2})$。描述阴影区域的矩形互不接触或相交。

输出格式

输出你需要在阳光刺眼的情况下行走的最短距离。你的答案的绝对或相对误差不得超过 $10^{-7}$。

样例 1

输入

2 1 7 5 1
3 6 5 9
2 3 6 5

输出

3.0

图 L.1 展示了一条从比赛地点到颁奖典礼地点的最优路径，该路径包含 $5$ 段。在第一段路程中，你背对太阳行走。在第二段和第四段路程中，你面向太阳行走，但处于阴影区域内。在第三段和第五段路程中，你在阴影区域外、面向太阳行走。这两段路程的总长度为 $3$。

样例 2

输入

2 0 10 10 0
2 7 3 8
4 3 8 5

输出

7.0

样例 3

输入

2 11 -1 -1 11
2 7 3 8
4 3 8 5

输出

0.0

样例 4

输入

3 1 5 9 5
-5 6 2 9
4 7 12 8
1 1 7 3

输出

0.0

样例 5

输入

3 1 7 9 3
2 6 3 8
4 4 5 6
6 2 7 4

输出

0.0

样例 6

输入

1 0 0 0 0
-5 -5 5 5

输出

0.0