ICPC 2025 · Problem L · Walking on Sunshine

I’m walking on sunshine, and it don’t feel good – my eyes hurt!

Baku has plenty of sunshine. If you walk away from the sun, or at least perpendicular to its rays, it does not shine in your eyes. For this problem assume that the sun shines from the south. Walking west or east or in any direction between west and east with a northward component avoids looking into the sun. Your eyes will hurt if you walk in any direction with a southward component.

Baku also has many rectangular areas of shade, and staying in these protects your eyes regardless of which direction you walk in. For example, Figure L.1 shows two shaded areas.

Find the minimum distance you need to walk with the sun shining in your eyes to get from the contest location to the awards ceremony location.

$x$ $y$

$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ NE NW

SW SE E N

W

S

• $\bullet$

contest

• $\bullet$

Figure L.1: Sample Input 1 and a path that minimizes the sun shining in your eyes.

Input

The first line of input contains five integers $n$, $x_{c}$, $y_{c}$, $x_{a}$, and $y_{a}$, where $n$ ($0\le n\le 10^{5}$) is the number of shaded areas, $(x_{c}, y_{c})$ is the location of the contest, and $(x_{a}, y_{a})$ is the location of the awards ceremony ($- 10 ^{6}\le xc, yc, xa, ya \le 10^{6}$). The sun shines in the direction $(0,1)$ from south towards north. You look into the sun if you walk in direction $(x, y)$ for any $y <0$ and any $x$.

The next $n$ lines describe the shaded areas, which are axis-aligned rectangles. Each of these lines contains four integers $x_{1}$, $y_{1}$, $x_{2}$, and $y_{2}$ ($- 10 ^{6}\le x1 < x2 \le 10^{6}$; $- 10 ^{6}\le y1 < y2 \le 10^{6}$). The southwest corner of the rectangle is $(x_{1}, y_{1})$ and its northeast corner is $(x_{2}, y_{2})$. The rectangles describing the shaded areas do not touch or intersect.

Output

Output the minimum distance you have to walk with the sun shining in your eyes. Your answer must have an absolute or relative error of at most $10^{- 7}$.

Sample Input 1

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

Sample Output 1

3.0

Explanation of Sample 1: Figure L.1 shows an optimal path from the contest location to the awards ceremony location with 5 segments. On the first segment you walk away from the sun. On the second and fourth segments you walk towards the sun but in a shaded area. On the third and fifth segments you walk towards the sun outside the shaded areas. The total length of these two segments is 3.

Sample Input 2

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

Sample Output 2

7.0

Sample Input 3

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

Sample Output 3

0.0

Sample Input 4

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

Sample Output 4

0.0

Sample Input 5

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

Sample Output 5

0.0

Sample Input 6

1 0 0 0 0
-5 -5 5 5

Sample Output 6

0.0