{"problem":{"name":"A. Atlantis","description":{"content":"21 December 2012, 21:13 (GMT-2), The Archipelago of the Azores. Crustal movements bring to the surface a never-before-seen island filled with exceptionally preserved pieces of ancient architecture. E","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":7000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10029A"},"statements":[{"statement_type":"Markdown","content":"21 December 2012, 21:13 (GMT-2), The Archipelago of the Azores.\n\nCrustal movements bring to the surface a never-before-seen island filled with exceptionally preserved pieces of ancient architecture. Exploration of this wonder is pending due to tons of sea water still covering the island.\n\nIts topology consists of multiple cylindrical elevations and depressions. You can view it as a set of platforms of varying height. Circles, which are the cylinders' bases, may enclose each other, but their rims never touch.\n\nAtlantis was built from highly waterproof material. Thus, the water cannot escape the depressed cylinders. Drilling through this priceless remnant of a civilization long gone is out of the question. Pumps will be used instead. Water removal will cost 1 / π per cubic meter.\n\nYour mundane task is to calculate the total cost of this endeavor.\n\nFirst line contains the number of test cases. Each of the test cases adheres to the following specification.\n\nThe first number in a test case is n (0 ≤ n ≤ 150000) – the number of cylinders. Each of the next n lines contain four natural numbers xi, yi, ri, hi ( - 106 ≤ xi, yi ≤ 106;0 < ri ≤ 106; - 100 ≤ hi ≤ 100;hi ≠ 0) – center of the i-th cylinder, its radius and the height of its interior relative to its exterior (all given in meters).\n\nFor each test case, output, in a single line, the cost of removing the remaining water from Atlantis.\n\n## Input\n\nFirst line contains the number of test cases. Each of the test cases adheres to the following specification.The first number in a test case is n (0 ≤ n ≤ 150000) – the number of cylinders. Each of the next n lines contain four natural numbers xi, yi, ri, hi ( - 106 ≤ xi, yi ≤ 106;0 < ri ≤ 106; - 100 ≤ hi ≤ 100;hi ≠ 0) – center of the i-th cylinder, its radius and the height of its interior relative to its exterior (all given in meters).\n\n## Output\n\nFor each test case, output, in a single line, the cost of removing the remaining water from Atlantis.\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, let $ n \\in \\mathbb{Z} $ be the number of cylinders, and let $ C = \\{(x_i, y_i, r_i, h_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of cylinders, where:  \n- $ (x_i, y_i) \\in \\mathbb{R}^2 $ is the center,  \n- $ r_i \\in \\mathbb{R}^+ $ is the radius,  \n- $ h_i \\in \\mathbb{R} \\setminus \\{0\\} $ is the relative height (positive = elevation, negative = depression).  \n\n**Constraints**  \n1. $ 0 \\leq n \\leq 150000 $  \n2. $ -10^6 \\leq x_i, y_i \\leq 10^6 $  \n3. $ 0 < r_i \\leq 10^6 $  \n4. $ -100 \\leq h_i \\leq 100, \\; h_i \\ne 0 $  \n\n**Objective**  \nCompute the total volume of water trapped in depressions, accounting for containment by enclosing elevations. Water is trapped only in depressions ($ h_i < 0 $) that are not fully enclosed by higher elevations.  \n\nDefine the *effective depth* of a depression $ i $ as:  \n$$\nd_i = \\min\\left( |h_i|, \\min_{\\substack{j: \\text{cylinder } j \\text{ encloses } i \\\\ h_j > 0}} h_j \\right)\n$$  \nif there exists an enclosing elevation $ j $, otherwise $ d_i = |h_i| $.  \n\nThe volume of water in cylinder $ i $ is:  \n$$\nV_i = \\pi r_i^2 \\cdot d_i \\cdot \\mathbb{I}_{h_i < 0}\n$$  \nwhere $ \\mathbb{I}_{h_i < 0} $ is the indicator function (1 if $ h_i < 0 $, else 0).  \n\nTotal cost (in currency units) is:  \n$$\n\\text{Cost} = \\frac{1}{\\pi} \\sum_{i=1}^{n} V_i = \\sum_{i=1}^{n} r_i^2 \\cdot d_i \\cdot \\mathbb{I}_{h_i < 0}\n$$  \n\n**Note**: Cylinder $ j $ encloses cylinder $ i $ iff $ \\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} + r_i < r_j $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10029A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}