{"problem":{"name":"D. Pulse Nova","description":{"content":"Mr.Panda is playing a game named Watcher of Samsara, a famous tower defense game developed by a Chinese studio. At the beginning of the game, every player is able to choose their first hero arbitraril","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10243D"},"statements":[{"statement_type":"Markdown","content":"Mr.Panda is playing a game named Watcher of Samsara, a famous tower defense game developed by a Chinese studio. At the beginning of the game, every player is able to choose their first hero arbitrarily from the hero pool which is randomly generated by the game system. Among all the heroes, Mr.Panda always chooses the hero named Leshrac, because of the character's ultimate skill, Pulse Nova.\n\nPulse Nova creates waves of damaging energy around Leshrac, one per second, to damage all nearby enemy units. This powerful skill inspires Mr.Panda to come up with a geometry problem.\n\nThere are $n$ straight lines on the 2D plane, where the $i^(t h)$ line passes two integer points $P_i$ and $Q_i$. You need to place a circle with radius of exactly $R$ on the plane. For each given line, there might be a segment part of this line that will be inside the circle. Please find a position for this circle to maximize the total length of all segment parts which will be inside the circle.\n\nThe first line of the input gives the number of test cases, $T$ $(1 <= T <= 100)$. $T$ test cases follow.\n\nThe first line of each test case contains two integers $n$ $(1 <= n <= 50)$ and $R$ $(1 <= R <= 3000)$, the number of straight lines, and the radius of the circle, respectively.\n\nIn the next $n$ lines, each contains four integers. In the $i^(t h)$ line, the first two integers indicate the 2D coordinates of point $P_i$, and the last two integers indicate the 2D coordinate of point $Q_i$. We ensure that $P_i != Q_i$ and the absolute value of every coordinate is not greater than $1000$.\n\nWe ensure the sum of $n$ in all test cases is not greater than $100$.\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the maximum length which will be inside the circle. Your answer will be considered correct if it is within an absolute or relative error of $10^(-6)$ when compared with the correct answer.\n\nFor the first sample, you can place the center of the circle at $(1, 1)$, so the total length inside the circle will be $8$.\n\nFor the second sample, you can place the center of the circle at $(0, 1)$, so the total length inside the circle will be $12 + 8 sqrt(2)$.\n\n## Input\n\nThe first line of the input gives the number of test cases, $T$ $(1 <= T <= 100)$. $T$ test cases follow.The first line of each test case contains two integers $n$ $(1 <= n <= 50)$ and $R$ $(1 <= R <= 3000)$, the number of straight lines, and the radius of the circle, respectively.In the next $n$ lines, each contains four integers. In the $i^(t h)$ line, the first two integers indicate the 2D coordinates of point $P_i$, and the last two integers indicate the 2D coordinate of point $Q_i$. We ensure that $P_i != Q_i$ and the absolute value of every coordinate is not greater than $1000$.We ensure the sum of $n$ in all test cases is not greater than $100$.\n\n## Output\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the maximum length which will be inside the circle. Your answer will be considered correct if it is within an absolute or relative error of $10^(-6)$ when compared with the correct answer.\n\n[samples]\n\n## Note\n\nFor the first sample, you can place the center of the circle at $(1, 1)$, so the total length inside the circle will be $8$.For the second sample, you can place the center of the circle at $(0, 1)$, so the total length inside the circle will be $12 + 8 sqrt(2)$.","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 $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of lines.  \n- Let $ R \\in \\mathbb{R}^+ $ be the fixed radius of the circle.  \n- For each line $ i \\in \\{1, \\dots, n_k\\} $, let $ \\ell_i $ be the infinite straight line passing through two distinct integer points $ P_i, Q_i \\in \\mathbb{Z}^2 $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ 1 \\le n_k \\le 50 $, and $ \\sum_{k=1}^T n_k \\le 100 $  \n3. $ 1 \\le R \\le 3000 $  \n4. Coordinates of $ P_i, Q_i $ are integers with absolute value $ \\le 1000 $, and $ P_i \\ne Q_i $  \n\n**Objective**  \nFind a point $ C \\in \\mathbb{R}^2 $ (center of the circle) such that the total length of the intersection segments between the circle $ \\mathcal{C}(C, R) $ and all lines $ \\ell_i $ is maximized.  \n\nThat is, maximize:  \n$$\n\\sum_{i=1}^{n_k} \\text{length}\\left( \\ell_i \\cap \\mathcal{C}(C, R) \\right)\n$$  \nwhere $ \\text{length}(\\ell_i \\cap \\mathcal{C}(C, R)) $ is the length of the chord (or 0 if no intersection) between line $ \\ell_i $ and the circle of radius $ R $ centered at $ C $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10243D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}