ACM 經典題：蛋糕切割（二分法求弦長）C語言完整解法

問題重述

半徑 R=1 的圓形蛋糕，一刀切成兩部分，面積比 a:b，求切口弦長。多組輸入，N=0 結束。

數學模型

• 圓心角 θ ∈ (0, π)，弦長 L = 2 sin(θ/2)。
• 扇形面積 S₁ = ½(θ - sin θ)，另一部分 S₂ = π - S₁。
• 要求 S₁ : S₂ = a : b（設 a ≤ b），即 S₁ * b = S₂ * a。

二分求解 θ

double area(double theta) { return (theta - sin(theta)) / 2.0; }

double chord(double a, double b) {
    double lo = 0, hi = acos(-1.0); // π
    for (int iter = 0; iter < 60; iter++) { // 雙精度足夠
        double mid = (lo + hi) / 2;
        double s1 = area(mid);
        double s2 = acos(-1.0) - s1;
        if (s1 * b <= s2 * a) lo = mid;
        else hi = mid;
    }
    return 2 * sin(lo / 2);
}

主程序框架

int main() {
    double a, b;
    while (scanf("%lf %lf", &a, &b) == 2) {
        if (a > b) { double t=a; a=b; b=t; } // 保證 a<=b
        printf("%.4f\n", chord(a, b));
    }
    return 0;
}

關鍵點

• 單調性保證二分正確：θ 增 → S₁ 增 → S₁/S₂ 增。
• 迭代 60 次足夠 double 精度收斂；也可用 fabs(hi-lo) > 1e-12 作條件。
• 輸出保留 4 位小數 %.4f。