A. Atlantis

Codeforces

IDCF10029A

Time7000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

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. Exploration of this wonder is pending due to tons of sea water still covering the island. Its 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. Atlantis 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. Your mundane task is to calculate the total cost of this endeavor. First 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). For each test case, output, in a single line, the cost of removing the remaining water from Atlantis. ## Input First 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). ## Output For each test case, output, in a single line, the cost of removing the remaining water from Atlantis. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For 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: - $ (x_i, y_i) \in \mathbb{R}^2 $ is the center, - $ r_i \in \mathbb{R}^+ $ is the radius, - $ h_i \in \mathbb{R} \setminus \{0\} $ is the relative height (positive = elevation, negative = depression). **Constraints** 1. $ 0 \leq n \leq 150000 $ 2. $ -10^6 \leq x_i, y_i \leq 10^6 $ 3. $ 0 < r_i \leq 10^6 $ 4. $ -100 \leq h_i \leq 100, \; h_i \ne 0 $ **Objective** Compute 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. Define the *effective depth* of a depression $ i $ as: $$ d_i = \min\left( |h_i|, \min_{\substack{j: \text{cylinder } j \text{ encloses } i \\ h_j > 0}} h_j \right) $$ if there exists an enclosing elevation $ j $, otherwise $ d_i = |h_i| $. The volume of water in cylinder $ i $ is: $$ V_i = \pi r_i^2 \cdot d_i \cdot \mathbb{I}_{h_i < 0} $$ where $ \mathbb{I}_{h_i < 0} $ is the indicator function (1 if $ h_i < 0 $, else 0). Total cost (in currency units) is: $$ \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} $$ **Note**: Cylinder $ j $ encloses cylinder $ i $ iff $ \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} + r_i < r_j $.

API Response (JSON)

{
  "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. E...",
      "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, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments