BestCoder Round #12 War：球與圓柱體交集體積比

BestCoder Round #12 War 題解

題目描述

國家 A 的領地為球體：x² + y² + z² ≤ R²
國家 B 的領地為圓柱體：x² + y² ≤ (HR)² 且 |z| ≤ HZ
兩國中心皆在原點，Z 軸對齊。求戰爭機率 P = V_intersection / V_union，精度 1e-6。

幾何分析

利用對稱性，僅考慮 z ≥ 0 部分再乘 2。設球半徑 R，圓柱半徑 r = HR，圓柱半高 h = HZ。

球在高度 z 的橫截面半徑：ρ(z) = √(R² - z²)

交集體積分類討論：

1. 圓柱完全在球內：r ≤ R 且 h ≤ √(R² - r²)
   交集體積 = 圓柱體積 = 2 * π * r² * h
2. 圓柱貫穿球體：r ≤ R 且 h > √(R² - r²)
   分兩段積分：z ∈ [0, d] 為圓柱全包含；z ∈ [d, min(h, R)] 為球面截面
   d = √(R² - r²)
3. 圓柱半徑大於球：r > R
   交集即為球體（若 h ≥ R）或球冠體積（若 h < R）

積分公式

球冠體積（高度 z）：V_cap(z) = π * R² * z - π * z³ / 3

核心程式碼

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double PI = acos(-1.0);

int main() {
    double R, HR, HZ;
    while (~scanf("%lf%lf%lf", &R, &HR, &HZ)) {
        double r = HR, h = HZ;
        double vc = 0.0;  // 交集體積
        
        if (r < R) {
            double d = sqrt(R*R - r*r);
            if (h <= d) {
                vc = 2 * PI * r * r * h;
            } else {
                double hh = min(h, R);
                double a = PI * R * R * hh - PI * hh * hh * hh / 3;
                double b = PI * R * R * d - PI * d * d * d / 3;
                vc = 2 * (PI * r * r * d + a - b);
            }
        } else {
            if (h <= R) {
                vc = 2 * (PI * R * R * h - PI * h * h * h / 3);
            } else {
                vc = 4.0/3 * PI * R * R * R;
            }
        }
        
        double vu = 4.0/3 * PI * R * R * R + 2 * PI * r * r * h - vc;
        printf("%.6lf\n", vc / vu);
    }
    return 0;
}

關鍵點

• 利用對稱性簡化計算，僅處理 z ≥ 0
• 分類討論覆蓋所有幾何相對位置關係
• 球冠體積公式推導自圓面積積分
• 雙精度足夠滿足 1e-6 精度要求