• 来源：48th Petrozavodsk Programming Camp, Winter 2025, Day 2: National Taiwan U Contest，Problem F
• 原题名：Flappy Bird
• 时间限制：1 秒
• 空间限制：1024 MiB

题目描述

佐伊最近重玩一款横版飞行游戏。屏幕可以看作一个矩形区域，左下角为 $(0,0)$，右上角为 $(L,H)$。飞鸟从左边界上的点 $(0,s)$ 出发，需要飞到右边界上的点 $(L,t)$。

游戏中有 $N$ 根竖直管道。第 $i$ 根管道位于横坐标 $x_i$ 处，从屏幕顶部到底部贯穿整条竖线，但中间留有一个可通过的缺口，缺口的纵坐标范围为 $[l_i,r_i]$。飞鸟被视为平面上的一个点，它的飞行轨迹可以是任意曲线。为了不撞上管道，轨迹在经过横坐标 $x_i$ 时，纵坐标必须落在区间 $[l_i,r_i]$ 内。

佐伊已经不满足于通关，她想知道：从 $(0,s)$ 飞到 $(L,t)$，并依次穿过所有管道缺口的最短路径长度是多少？

请你计算这个最短长度。

【插图提示】此题原题样例带有示意图。建议在题面中加入一张图：矩形区域中有三根位于 $x=2,5,7$ 的竖直管道，缺口分别为 $[2,5]$、$[0,2]$、$[3,6]$，并用一条红色曲线表示从 $(0,0)$ 到 $(9,11)$ 的最短可行航线。

输入格式

第一行包含五个整数 $N,L,H,s,t$，含义如题目描述所述。

接下来 $N$ 行，每行包含三个整数 $x_i,l_i,r_i$，表示第 $i$ 根管道的位置与缺口范围。

注意，输入中的 $x_i$ 互不相同，但不保证按从小到大的顺序给出。

输出格式

输出一个实数，表示从起点到终点的最短路径长度。

若你的答案为 $a$，标准答案为 $b$，当满足

时，答案会被认为正确。

数据范围

• $1\le N\le 3\times 10^5$；
• $1\le L,H\le 10^9$；
• $0\le s,t\le H$；
• $0<x_i<L$；
• $0\le l_i<r_i\le H$；
• 所有 $x_i$ 互不相同。

样例 1

输入

3 9 11 0 11
2 2 5
5 0 2
7 3 6

输出

15.68572788688027230819