Rudolph and Christmas Tree (Codeforces 1846D)
Tags: Math, geometry

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.The tree is a vertical trunk with identical triangular branches at different heights. The thickness of the trunk is negligible.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$$$.The figure below shows an example of a tree with $$$d = 4, h = 2$$$ and three branches with bases at heights $$$[1, 4, 5]$$$.  Help Rudolph calculate the total area of the tree branches.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Then follow the descriptions of the test cases.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.The second line of each test case contains $$$n$$$ integers $$$y_i$$$ $$$(1 \le y_i \le 10^9, y_1 < y_2 < ... < y_n)$$$ — the heights of the bases of the branches.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: 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}$$$.


Sample Inputs:
5
3 4 2
1 4 5
1 5 1
3
4 6 6
1 2 3 4
2 1 200000
1 200000
2 4 3
9 11

Sample Outputs:
11
2.5
34.5
199999.9999975
11.333333

Solution (Python):
import sys

def solve() -> None:
    (n, b, h) = map(int, sys.stdin.readline().split())
    x = list(map(int, sys.stdin.readline().split()))
    x.sort()
    c = 0
    a = []
    for i in range(n):
        if c > x[i]:
            a.append(c - x[i])
        c = x[i] + h
    cnt = 0
    ans = n * b * h
    ans /= 2
    for i in a:
        cnt += i * i
    cnt *= b
    cnt /= 2
    cnt /= h
    ans -= cnt
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
def main():
    t = int(input())
    results = []
    for i in range(t):
        (n, d, h) = map(int, input().split())
        y = list(map(int, input().split()))
        results.append(solution(n, d, h, y))
    print('\n'.join(map(str, results)))

def solution(n, d, h, y):
    s = d * h
    result = s
    yp = y[0]
    for i in range(1, n):
        result += s
        g = y[i] - yp
        if g < h:
            result -= (d - d * g / h) * (h - g)
        yp = y[i]
    return result / 2
main()

Solution (Python):
from io import StringIO
import sys

def main():
    out = StringIO()
    get_line = sys.stdin.readline

    def get_ints():
        return map(int, get_line().split(' '))

    def get_int():
        return int(get_line())
    for i in range(get_int()):
        (n, d, h) = get_ints()
        y = list(get_ints())
        a = d * h * 0.5
        ans = a
        for j in range(len(y) - 1):
            ol = h - (y[j + 1] - y[j])
            ans += a
            if ol > 0:
                bol = d * (ol / h)
                aol = 0.5 * bol * ol
                ans -= aol
        out.write(str(ans))
        out.write('\n')
    sys.stdout.write(out.getvalue())
if __name__ == '__main__':
    main()