codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1846D.md (2062B)


      1 Source: https://codeforces.com/problemset/problem/1846/D
      2 
      3 D. Rudolph and Christmas Tree
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Rudolph drew a beautiful Christmas tree and decided to print the picture. However, the ink in the cartridge often runs out at the most inconvenient moment. Therefore, Rudolph wants to calculate in advance how much green ink he will need.
     22 
     23 The tree is a vertical trunk with identical triangular branches at different heights. The thickness of the trunk is negligible.
     24 
     25 Each branch is an isosceles triangle with base $d$ and height $h$, whose base is perpendicular to the trunk. The triangles are arranged upward at an angle, and the trunk passes exactly in the middle. The base of the $i$-th triangle is located at a height of $y_i$.
     26 
     27 The figure below shows an example of a tree with $d = 4, h = 2$ and three branches with bases at heights $[1, 4, 5]$.
     28 
     29  ![](https://espresso.codeforces.com/fae4a21965677442ad9a0104337cb0b03b7bc84a.png) 
     30 
     31 Help Rudolph calculate the total area of the tree branches.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 Then follow the descriptions of the test cases.
     38 
     39 The first line of each test case contains three integers $n, d, h$ ($1 \le n, d, h \le 2 \cdot 10^5$) — the number of branches, the length of the base, and the height of the branches, respectively.
     40 
     41 The second line of each test case contains $n$ integers $y_i$ $(1 \le y_i \le 10^9, y_1 \lt y_2 \lt ... \lt y_n)$ — the heights of the bases of the branches.
     42 
     43 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output a single real number on a separate line — the total area of the tree branches. The answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 3 4 2
     57 
     58 1 4 5
     59 
     60 1 5 1
     61 
     62 3
     63 
     64 4 6 6
     65 
     66 1 2 3 4
     67 
     68 2 1 200000
     69 
     70 1 200000
     71 
     72 2 4 3
     73 
     74 9 11
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 11
     81 2.5
     82 34.5
     83 199999.9999975
     84 11.333333
     85 ```