{"problem":{"name":"B. Street","description":{"content":"As everyone knows. The last ACM-ICPC was in Phuket, Thailand. One thing about Phuket is that it has a very hot weather. So walking in the sunlight is a harder task than you might think! Joud was walk","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10114B"},"statements":[{"statement_type":"Markdown","content":"As everyone knows. The last ACM-ICPC was in Phuket, Thailand. One thing about Phuket is that it has a very hot weather. So walking in the sunlight is a harder task than you might think!\n\nJoud was walking in one of the famous markets of the city. One street was full of flower shops. Joud hates flowers, so he decided to go through this street while walking the minimum distance possible in sunlight.\n\nFortunately, some of the shops have big umbrellas placed in front of them, forming rectangular shadow spots.\n\nGiven the positions of these spots. What's the minimum distance that Joud has to walk in the sunlight in order to get to the end of the street?\n\nNote that the street is a rectangular shape and Joud can start from any point at the start line and wants to reach any point at the end line of the street.\n\nThe first line of the input will contain T the number of test cases.\n\nEach test case starts with three integers on a single line (0 < N ≤ 100), the number of rectangular spots, (0 < L ≤ 109), the length of the street, (0 < U ≤ 109), the width of the street.\n\nThen N lines follow, each describes a rectangular spot and contains four integers (0 < h ≤ 109), the height of the spot ,(0 < w ≤ 109), the width of the spot , (0 ≤ d ≤ 109), the distance between the beginning of the street and the spot , (). If k is equal to 1 it means that the spot is sharing a side with the right side of the street, otherwise it's sharing a side with the left side of the street. It's guaranteed that there is no overlapping between spots, but they might touch. See the figure below.\n\nFor each test case print one number rounded to exactly 6 places after the decimal point. The solution to the problem above.\n\nThe next figure shows a possible solution for the second sample. \n\n## Input\n\nThe first line of the input will contain T the number of test cases.Each test case starts with three integers on a single line (0 < N ≤ 100), the number of rectangular spots, (0 < L ≤ 109), the length of the street, (0 < U ≤ 109), the width of the street.Then N lines follow, each describes a rectangular spot and contains four integers (0 < h ≤ 109), the height of the spot ,(0 < w ≤ 109), the width of the spot , (0 ≤ d ≤ 109), the distance between the beginning of the street and the spot , (). If k is equal to 1 it means that the spot is sharing a side with the right side of the street, otherwise it's sharing a side with the left side of the street. It's guaranteed that there is no overlapping between spots, but they might touch. See the figure below.\n\n## Output\n\nFor each test case print one number rounded to exactly 6 places after the decimal point. The solution to the problem above.\n\n[samples]\n\n## Note\n\nThe next figure shows a possible solution for the second sample.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of rectangular shadow spots.  \n- Let $ L \\in \\mathbb{R}^+ $ be the length of the street.  \n- Let $ U \\in \\mathbb{R}^+ $ be the width of the street.  \n- Let $ S = \\{ (h_i, w_i, d_i, k_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of shadow spots, where:  \n  - $ h_i \\in \\mathbb{R}^+ $: height of spot $ i $,  \n  - $ w_i \\in \\mathbb{R}^+ $: width of spot $ i $,  \n  - $ d_i \\in \\mathbb{R}^+ $: distance from start of street to spot $ i $,  \n  - $ k_i \\in \\{0, 1\\} $: orientation (0 = left-aligned, 1 = right-aligned).  \n\nEach spot $ i $ defines a rectangular shadow region:  \n- If $ k_i = 0 $: spans horizontally from $ x = 0 $ to $ x = w_i $, vertically from $ y = d_i $ to $ y = d_i + h_i $.  \n- If $ k_i = 1 $: spans horizontally from $ x = U - w_i $ to $ x = U $, vertically from $ y = d_i $ to $ y = d_i + h_i $.  \n\n**Constraints**  \n1. $ 0 < T \\leq 100 $  \n2. $ 0 < N \\leq 100 $  \n3. $ 0 < L \\leq 10^9 $  \n4. $ 0 < U \\leq 10^9 $  \n5. $ 0 < h_i, w_i \\leq 10^9 $  \n6. $ 0 \\leq d_i \\leq 10^9 $  \n7. $ k_i \\in \\{0, 1\\} $  \n8. Spots do not overlap (may touch).  \n\n**Objective**  \nFind the minimum distance Joud must walk in sunlight to traverse from the start line ($ y = 0 $) to the end line ($ y = L $), starting at any point on $ y = 0 $ and ending at any point on $ y = L $, while moving continuously through the 2D plane $ [0, U] \\times [0, L] $.  \n\nThe path may pass through shadow regions (no cost) or sunlight regions (cost = Euclidean distance). The total cost is the length of the path through sunlight.  \n\nEquivalently:  \nFind the shortest path from the bottom edge $ \\{ (x, 0) \\mid x \\in [0, U] \\} $ to the top edge $ \\{ (x, L) \\mid x \\in [0, U] \\} $, where movement is allowed everywhere, but only the portion of the path outside all shadow rectangles contributes to the cost.  \n\nThis reduces to:  \nCompute the shortest path in the free space $ ([0,U] \\times [0,L]) \\setminus \\bigcup_{i=1}^N R_i $, where $ R_i $ is the rectangle of spot $ i $, using Euclidean distance.  \n\n**Note**: The problem is equivalent to finding the shortest path avoiding obstacles (rectangles), with start and goal as entire edges. This can be solved via visibility graph or by modeling reachable intervals on horizontal slices.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10114B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}