{"problem":{"name":"G. Radar Scanner","description":{"content":"There are $n$ rectangle radar scanners on the ground. The sides of them are all paralleled to the axes. The $i$-th scanner's bottom left corner is square $(a_i, b_i)$ and its top right corner is squar","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222G"},"statements":[{"statement_type":"Markdown","content":"There are $n$ rectangle radar scanners on the ground. The sides of them are all paralleled to the axes. The $i$-th scanner's bottom left corner is square $(a_i, b_i)$ and its top right corner is square $(c_i, d_i)$. Each scanner covers some squares on the ground.\n\nYou can move these scanners for many times. In each step, you can choose a scanner and move it one square to the left, right, upward or downward.\n\nToday, the radar system is facing a critical low-power problem. You need to move these scanners such that there exists a square covered by all scanners.\n\nYour task is to minimize the number of move operations to achieve the goal.\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of radar scanners.\n\nFor the next $n$ lines, each line contains four integers $a_i, b_i, c_i, d_i (1 <= a_i, b_i, c_i, d_i <= 10^9, a_i <= c_i, b_i <= d_i)$, denoting each radar scanner.\n\nIt is guaranteed that $sum n <= 10^6$.\n\nFor each test case, print a single line containing an integer, denoting the minimum number of steps.\n\n## Input\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of radar scanners.For the next $n$ lines, each line contains four integers $a_i, b_i, c_i, d_i (1 <= a_i, b_i, c_i, d_i <= 10^9, a_i <= c_i, b_i <= d_i)$, denoting each radar scanner.It is guaranteed that $sum n <= 10^6$.\n\n## Output\n\nFor each test case, print a single line containing an integer, denoting the minimum number of steps.\n\n[samples]","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 cities, and $ k \\in \\mathbb{Z} $ the number of factories to place.  \n- Let $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $, where each edge $ e \\in E $ has weight $ w(e) \\in \\mathbb{Z}^+ $.  \n- Let $ L \\subseteq V $ be the set of leaf nodes (degree-1 vertices), with $ |L| \\geq k $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^3 $  \n2. $ 2 \\leq n \\leq 10^5 $, $ 1 \\leq k \\leq 100 $  \n3. $ 1 \\leq w(e) \\leq 10^5 $ for all $ e \\in E $  \n4. $ |L| \\geq k $  \n5. Sum of $ n $ across all test cases $ \\leq 10^6 $  \n\n**Objective**  \nSelect a subset $ S \\subseteq L $ with $ |S| = k $ such that the sum of pairwise distances between all pairs of selected leaves is minimized:  \n$$\n\\min_{\\substack{S \\subseteq L \\\\ |S| = k}} \\sum_{\\substack{u, v \\in S \\\\ u < v}} d(u, v)\n$$  \nwhere $ d(u, v) $ is the shortest path distance (sum of edge weights) between nodes $ u $ and $ v $ in $ G $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}