喵哈喽~ 各位算法大师们好呀！我是你们的小助手猫娘，今天又要和大家一起解决一道有趣的题目啦！这次我们要帮助一位叫 Rudolph 的朋友计算他画的圣诞树的面积，他担心打印的时候墨水会不够用，真是个细心又有点可爱的小烦恼呢，嘻嘻~

那么，就让我们伸出爪子，一起来帮他解决这个问题吧！

Problem ID: 1846D - Rudolph and Christmas Tree

---

题目大意

这道题是酱紫的喵：

Rudolph 画了一棵圣诞树。这棵树由一根垂直的树干和许多全等的三角形树枝组成。树干的宽度可以忽略不计。

每个树枝都是一个底为 d，高为 h 的等腰三角形。这些三角形的底边都垂直于树干，并且树干正好穿过底边的中点。第 i 个树枝的底边位于高度 y_i 处。题目保证输入的 y_i 是从小到大排好序的哦。

就像上图一样，不同的树枝可能会相互重叠。我们的任务就是，计算出所有树枝覆盖的总面积（重叠部分只算一次哦）。

题解方法

拿到题目，猫娘的第一反应是：哇，好多三角形！如果它们都不重叠，那该多好呀！

一个三角形的面积是 0.5 * d * h。如果有 n 个，那总面积就是 n * 0.5 * d * h 啦。这是一个很好的起点！我们可以先假设所有树枝都是分开的，算出这个“理论最大总面积”。

但是...但是！现实是残酷的，树枝会重叠呀！就像猫猫的爪子叠在一起一样，重叠的部分我们就算了两次，所以要把多算的那部分减掉才行，喵。

那重叠部分怎么算呢？

我们只需要考虑相邻的两个三角形。因为 y 数组是排好序的，所以我们只需要比较第 i-1 个和第 i 个三角形。

• 第 i-1 个三角形（下面的那个）的底边在 y_{i-1}，它的尖尖最高能到 y_{i-1} + h。
• 第 i 个三角形（上面的那个）的底边在 y_i。

如果 y_i 大于或者等于 y_{i-1} + h，说明上面那个三角形的底边在下面那个三角形的尖尖之上，它们俩就像害羞的猫咪一样，碰都碰不到，自然没有重叠啦。

但如果 y_i < y_{i-1} + h，哎呀！它们贴在一起了！上面那个三角形把下面那个三角形的“小尖尖”给盖住了。

这个被盖住的部分，本身也是一个小的等腰三角形。它和我们原来的大三角形（底d高h）是相似的！

这个重叠小三角的高度 h_overlap 是多少呢？就是下面大三角形的尖尖超出了上面大三角形底边的部分，也就是 (y_{i-1} + h) - y_i，整理一下就是 h - (y_i - y_{i-1})。

根据相似三角形的性质，面积的比等于相似比（也就是高度比）的平方。 所以： 重叠面积 / 单个大三角形面积 = (h_overlap / h)^2

于是，我们就算出了重叠部分的面积： area_overlap = (0.5 * d * h) * (h_overlap / h)^2

我们的完整算法就出来啦：

1. 先计算出理论上的总面积 total_area = n * 0.5 * d * h。
2. 从第二个三角形开始，依次遍历到最后一个 (i 从 1 到 n-1)。
3. 对于每个三角形 i，都和它前一个 i-1 比较。
4. 计算它们的高度差 delta_y = y_i - y_{i-1}。
5. 如果 delta_y < h，说明它们重叠了。
6. 计算重叠小三角形的高度 h_overlap = h - delta_y。
7. 根据相似三角形性质，计算出重叠面积 area_overlap。
8. 从 total_area 中减去这个 area_overlap。
9. 遍历完所有相邻的三角形对之后，total_area 就是我们最终的答案啦！

因为计算中会有除法，可能会产生小数，所以整个计算过程都要用 double 类型的变量来处理，这样才能保证精度足够高，不会出错哦，喵~

题解

这是C++的实现代码，猫娘加了一些注释，方便大家理解哦~

#include <iostream>
#include <vector>
#include <iomanip> // 别忘了这个头文件，控制输出精度要用它
#include <cmath>

void solve() {
    long long n;
    double d, h; // 用 double 来读取 d 和 h，避免后续转换的麻烦
    std::cin >> n >> d >> h;
    std::vector<long long> y(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> y[i];
    }

    // 一个树枝的面积
    double single_area = 0.5 * d * h;
    
    // 先天真地把所有三角形面积加起来，喵~
    double total_area = n * single_area;

    // 从下往上，检查相邻树枝的重叠情况
    for (int i = 1; i < n; ++i) {
        // 两个相邻树枝底座的高度差
        double delta_y = y[i] - y[i - 1];
        
        // 检查一下，这两个小爪子...啊不，小树枝有没有叠在一起
        if (delta_y < h) {
            // 如果高度差小于一个树枝的高度，说明它们重叠了
            
            // 计算被遮住的那个小三角形的高度
            double h_overlap = h - delta_y;
            
            // 用相似三角形的魔法来计算重叠面积！
            // 面积比 = 相似比的平方 (相似比 = 高度比)
            double ratio = h_overlap / h;
            double area_overlap = single_area * ratio * ratio;
            
            // 从总面积里把多算的这块减掉
            total_area -= area_overlap;
        }
    }

    // 输出最终结果，用 setprecision 保证精度足够
    std::cout << std::fixed << std::setprecision(10) << total_area << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然不难，但里面藏着一些很重要的知识点哦，就像猫咪藏起来的宝藏一样！

1. 相似三角形 (Similar Triangles)

   • 定义: 相似三角形就是形状完全相同，但大小可能不同的三角形。它们的对应角相等，对应边成比例。这个比例被称为“相似比”。
   • 重要性质: 在这道题里，我们用到了一个超级有用的性质：相似三角形的面积比等于相似比的平方。
   • Area1 / Area2 = (Side1 / Side2)^2 = (Height1 / Height2)^2
   • 正是利用这个性质，我们才能通过重叠部分的高度，快速算出它的面积，而不需要重新计算它的底边长。

2. 浮点数精度 (Floating-Point Precision)

   • 在算法竞赛中，只要题目涉及到除法或者要求输出小数，我们就得特别小心精度问题。
   • int 或 long long 只能存整数，无法表示小数。
   • float 和 double 是用来存储浮点数（也就是小数）的类型。double 的精度比 float 更高，通常在比赛中，我们优先使用 double 来避免不必要的精度损失。
   • 在本题中，面积计算 0.5 * d * h 和比例计算 h_overlap / h 都可能产生小数，所以必须使用 double 来存储面积相关的变量。
   • 输出时使用 std::fixed 和 std::setprecision(10) 可以确保我们输出的是带有10位小数的浮点数，满足题目的精度要求。

3. 贪心思想与差分思想的影子

   • 我们的解法其实也带有一点点贪心和差分的味道。我们先“贪心地”把所有面积都加上，然后再通过计算相邻项的“差”（重叠部分），把多余的减掉。这种“先加后减”的修正思想在很多问题中都非常有效！

好啦，今天的解题分享就到这里啦！希望猫娘的讲解能帮到你。只要掌握了相似三角形的魔法，这类几何问题就会变得像撸猫一样简单又愉快哦！下次再见，喵~