NekoNowcoder

Appearance

KeyboardFree - 题解 ​

标签与难度 ​

标签: 计算几何, 期望, 数值积分, 蒙特卡洛方法, 数学 难度: 1700

题目大意喵~ ​

你好呀，指挥官！这道题是说，我们有三个圆心都在原点的同心圆，它们的半径分别是 r1,r2,r3r_1, r_2, r_3 呐。有三个点 A, B, C 分别在这三个圆上自由地移动。我们的任务是，计算出这三个点组成的三角形 △ABC\triangle ABC 的面积的期望值是多少，喵~

简单来说，就是想象 A, B, C 在各自的轨道上随机乱跑，我们想知道它们围成的三角形的平均大小是多少。

解题思路分析 ​

这道题看起来和几何还有概率期望有关，感觉有点复杂？别怕别怕，让我带你一步步解开它的神秘面纱，就像解开一个毛线球一样，喵~

步骤一：建立坐标系，描述问题 ​

首先，我们把三个同心圆的圆心放在坐标系的原点 (0,0)(0, 0)。 点 A 在半径为 r1r_1 的圆上，它的坐标可以表示为 (r1cos⁡θ1,r1sin⁡θ1)(r_1 \cos\theta_1, r_1 \sin\theta_1)。 点 B 在半径为 r2r_2 的圆上，坐标是 (r2cos⁡θ2,r2sin⁡θ2)(r_2 \cos\theta_2, r_2 \sin\theta_2)。 点 C 在半径为 r3r_3 的圆上，坐标是 (r3cos⁡θ3,r3sin⁡θ3)(r_3 \cos\theta_3, r_3 \sin\theta_3)。

这里的 θ1,θ2,θ3\theta_1, \theta_2, \theta_3 是三个点各自与 x 轴正方向的夹角。因为点是随机移动的，我们可以认为这三个角度在 [0,2π)[0, 2\pi) 这个区间内是均匀分布的，而且它们之间相互独立。

三角形的面积可以用坐标来计算，一个常用的公式是“鞋带公式”（或者叫行列式、叉积法）：

S△ABC=12∣xA(yB−yC)+xB(yC−yA)+xC(yA−yB)∣S_{\triangle ABC} = \frac{1}{2} |x_A(y_B - y_C) + x_B(y_C - y_A) + x_C(y_A - y_B)|

把点的坐标代入，我们就能得到一个只跟 θ1,θ2,θ3\theta_1, \theta_2, \theta_3 有关的面积表达式。

步骤二：期望值的“恐怖”积分 ​

要求面积的期望值 E[S]E[S]，按照定义，我们需要对所有可能的角度组合计算面积，然后求平均。在连续情况下，这就是一个三重积分，喵！

E[S]=1(2π)3∫02π∫02π∫02πS(θ1,θ2,θ3) dθ1 dθ2 dθ3E[S] = \frac{1}{(2\pi)^3} \int_0^{2\pi} \int_0^{2\pi} \int_0^{2\pi} S(\theta_1, \theta_2, \theta_3) \, d\theta_1 \, d\theta_2 \, d\theta_3

Nyaa~！这个积分看起来就超级可怕，对吧？我的胡须都吓得抖了一下！直接去解这个积分几乎是不可能的任务。所以，我们得想个聪明的办法绕过去。

步骤三：利用对称性简化问题 ​

这时候就要发挥我的敏锐观察力了！注意到这三个圆是同心圆，整个系统具有旋转对称性。 这意味着，无论我们把整个坐标系旋转多少度，A, B, C 三个点形成的三角形的面积分布情况是不会改变的。它们的相对位置关系才是决定面积的关键。

所以，我们可以使用一个小小的“魔法”，就是把整个系统旋转一下，让其中一个点固定在一个方便计算的位置，而最终的期望面积是不会变的！ 比如说，我们把点 A 固定在它所在圆的 (r1,0)(r_1, 0) 这个位置上。这相当于我们把 θ1\theta_1 固定为 00。

这样一来，三重积分就降维成了双重积分！

  • A 点坐标: (r1,0)(r_1, 0)
  • B 点坐标: (r2cos⁡θ2,r2sin⁡θ2)(r_2 \cos\theta_2, r_2 \sin\theta_2)
  • C 点坐标: (r3cos⁡θ3,r3sin⁡θ3)(r_3 \cos\theta_3, r_3 \sin\theta_3)

现在，我们只需要在 θ2\theta_2 和 θ3\theta_3 从 00 到 2π2\pi 的范围内求平均面积就行啦！

E[S]=1(2π)2∫02π∫02πS(0,θ2,θ3) dθ2 dθ3E[S] = \frac{1}{(2\pi)^2} \int_0^{2\pi} \int_0^{2\pi} S(0, \theta_2, \theta_3) \, d\theta_2 \, d\theta_3

步骤四：用离散化近似连续积分 ​

虽然双重积分比三重积分好一点，但直接计算还是很难。这时候，我们可以用一种非常强大的近似方法：数值积分。

它的思想很简单：既然连续地取所有角度太难，那我们就在圆上取很多很多个离散的点，用这些离散点位置的平均面积来近似期望面积。这就像用很多小小的直线段来拼成一个圆一样，只要取的点足够多，结果就会非常接近真实值，呐！

这就是所谓的蒙特卡洛方法的一种体现。我们的算法就清晰了：

  1. 选择一个足够大的整数 K（比如 1000 或 2000），作为我们在每个圆上采样的点的数量。
  2. 将 [0,2π)[0, 2\pi) 这个角度区间平均分成 K 份，每份的角度是 Δθ=2π/K\Delta\theta = 2\pi/K。
  3. 固定点 A 在 (r1,0)(r_1, 0)。
  4. 使用两层循环：
    • 外层循环让点 B 遍历它所在圆上的 K 个采样点。第 i 个点的角度是 i⋅Δθi \cdot \Delta\theta。
    • 内层循环让点 C 遍历它所在圆上的 K 个采样点。第 j 个点的角度是 j⋅Δθj \cdot \Delta\theta。
  5. 在循环内部，我们有了 A, B, C 的一组具体坐标，计算出 △ABC\triangle ABC 的面积。
  6. 把所有计算出的面积累加起来，最后除以总的组合数 (K×KK \times K)，就得到了我们想要的期望面积的近似值。

这个方法把复杂的积分问题，变成了一个简单的编程循环问题，是不是很巧妙呀，喵~

一个小细节：由于问题的对称性，我们把哪个点固定在哪个圆上，或者说，半径 r1,r2,r3r_1, r_2, r_3 的顺序其实不影响最终结果。所以有些代码里会对半径排序，但这并不是必须的哦。

代码实现 ​

下面就是我根据上面的思路，精心为你准备的代码啦！注释写得很详细，希望能帮你理解每一行代码的作用，喵~

cpp
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

// 使用 long double 来保证精度，喵~
using LD = long double;

// 定义一个常量 PI
const LD PI = acosl(-1.0L);

// 计算三个点 (x1, y1), (x2, y2), (x3, y3) 组成的三角形面积
// 这里用的是叉积公式的绝对值的一半
LD triangle_area(LD x1, LD y1, LD x2, LD y2, LD x3, LD y3) {
    return std::abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2.0L;
}

void solve() {
    LD r1, r2, r3;
    std::cin >> r1 >> r2 >> r3;

    // 在圆上采样的点的数量，K越大结果越精确，但计算时间也越长
    const int K_SAMPLES = 1000;

    // 预先计算好所有采样点需要的 sin 和 cos 值，避免在循环中重复计算，提高效率！
    std::vector<LD> cos_vals(K_SAMPLES);
    std::vector<LD> sin_vals(K_SAMPLES);
    for (int i = 0; i < K_SAMPLES; ++i) {
        LD angle = 2.0L * PI * i / K_SAMPLES;
        cos_vals[i] = cosl(angle);
        sin_vals[i] = sinl(angle);
    }
    
    LD total_area = 0.0L;

    // 固定点 A 在 (r1, 0)
    LD ax = r1, ay = 0.0L;

    // 遍历点 B 在圆 r2 上的所有 K_SAMPLES 个采样位置
    for (int i = 0; i < K_SAMPLES; ++i) {
        LD bx = r2 * cos_vals[i];
        LD by = r2 * sin_vals[i];

        // 遍历点 C 在圆 r3 上的所有 K_SAMPLES 个采样位置
        for (int j = 0; j < K_SAMPLES; ++j) {
            LD cx = r3 * cos_vals[j];
            LD cy = r3 * sin_vals[j];
            
            // 计算当前这个三角形的面积，并累加到总面积中
            total_area += triangle_area(ax, ay, bx, by, cx, cy);
        }
    }

    // 平均面积 = 总面积 / 采样总数
    // 总共有 K_SAMPLES * K_SAMPLES 种组合
    LD expected_area = total_area / (K_SAMPLES * K_SAMPLES);
    
    // 按题目要求格式输出结果
    std::cout << std::fixed << std::setprecision(1) << expected_area << "\n";
}

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

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

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(K2)O(K^2) 每个测试用例。 我们的核心计算是两个嵌套的循环，每个循环都执行 K_SAMPLES 次（我们代码里是 K）。所以总的计算量是 K×KK \times K 次面积计算。预计算 sin 和 cos 的时间是 O(K)O(K)，可以忽略不计。所以总时间复杂度是 O(K2)O(K^2)。

  • 空间复杂度: O(K)O(K) 我们为了提高效率，预先存储了 K 个 sin 值和 K 个 cos 值。所以需要 O(K)O(K) 的额外空间来存放这两个数组。

知识点总结 ​

这道题虽然看起来是道几何难题，但真正的核心却是用数值方法解决问题的思想，喵~

  1. 期望值问题: 当直接计算期望的积分形式非常复杂时，可以考虑使用蒙特卡洛方法或数值积分进行近似。
  2. 对称性: 学会发现并利用问题中的对称性（比如本题的旋转对称性）是简化问题的关键一步，它可以大大减少计算量。
  3. 数值积分: 将连续的积分问题转化为离散的求和问题是一种非常实用且强大的技巧。通过在定义域内大量均匀采样，用样本均值来估计期望值。
  4. 计算几何基础: 知道如何用坐标计算三角形面积是解决本题的基础。鞋带公式（或叉积）是一个必须掌握的工具哦！

希望这篇题解能帮到你！如果还有不懂的地方，随时可以再来问我哦，喵~