{"problem":{"name":"I. Сопротивление","description":{"content":"После успешного побега из здания подземной тюрьмы Галактической федерации соратники Сопротивления захватили бронированный автомобиль и теперь они должны добраться из точки P = (0, 0) в точку Q = (0, Y","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136I"},"statements":[{"statement_type":"Markdown","content":"После успешного побега из здания подземной тюрьмы Галактической федерации соратники Сопротивления захватили бронированный автомобиль и теперь они должны добраться из точки P = (0, 0) в точку Q = (0, Yq). \n\nЗадача усложняется тем, что вокруг тюрьмы возведено множество стен, и чтобы покинуть тюрьму необходимо проехать последовательно через N ворот, которые представляет собой параллельные оси OX отрезки. \n\nВам необходимо посчитать длину кратчайшего пути из точки P в точку Q при условии, что путь должен проходить последовательно сквозь каждые ворота.\n\nВ первой строке задано число ворот N (1 ≤ N ≤ 105).\n\nВо второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).\n\nВ следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1,  - 109 ≤ Xil < Xir ≤ 109).\n\nВсе числа во входных данных целые.\n\nВыведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.\n\nКратчайший путь для теста из примера показан на рисунке:\n\n## Входные Данные\n\nВ первой строке задано число ворот N (1 ≤ N ≤ 105).Во второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).В следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1,  - 109 ≤ Xil < Xir ≤ 109).Все числа во входных данных целые.\n\n## Выходные Данные\n\nВыведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.\n\n## Пример\n\nВходные данные351 -1 13 1 24 -2 -1Выходные данные6.812559200041\n\n## Примечание\n\nКратчайший путь для теста из примера показан на рисунке:  \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of gates.  \nLet $ Y_q \\in \\mathbb{R} $ be the $ y $-coordinate of the destination point $ Q = (0, Y_q) $.  \nLet $ P = (0, 0) $ be the starting point.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let the $ i $-th gate be a horizontal segment $ G_i = [X_{i,l}, X_{i,r}] \\times \\{Y_i\\} $, where $ 0 < Y_i < Y_q $ and $ Y_i < Y_{i+1} $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 2 \\leq Y_q \\leq 10^9 $  \n3. For each $ i \\in \\{1, \\dots, N\\} $:  \n   - $ -10^9 \\leq X_{i,l} < X_{i,r} \\leq 10^9 $  \n   - $ 0 < Y_i < Y_q $  \n   - $ Y_i < Y_{i+1} $ (gates are ordered by increasing $ y $-coordinate)\n\n**Objective**  \nFind the minimum length of a path from $ P = (0, 0) $ to $ Q = (0, Y_q) $ that intersects each gate $ G_i $ in order (i.e., the path must pass through some point $ (x_i, Y_i) \\in G_i $ for each $ i $, and the sequence of points $ (0,0), (x_1,Y_1), (x_2,Y_2), \\dots, (x_N,Y_N), (0,Y_q) $ forms a polygonal chain).\n\nThe total path length is:  \n$$\nL = \\sum_{i=0}^{N} \\sqrt{(x_{i+1} - x_i)^2 + (Y_{i+1} - Y_i)^2}\n$$  \nwhere $ x_0 = 0 $, $ Y_0 = 0 $, $ x_{N+1} = 0 $, $ Y_{N+1} = Y_q $, and $ x_i \\in [X_{i,l}, X_{i,r}] $ for $ i \\in \\{1, \\dots, N\\} $.\n\nMinimize $ L $ over all valid choices of $ x_1, \\dots, x_N $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}