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  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 ```