HDU 2080 夾角有多大 II：向量夾角餘弦公式求解

HDU 2080 給定兩點 (x1,y1)、(x2,y2)，求它們與原點連線的夾角（0°~180°）。本文推導餘弦公式解法，分析數值穩定性，給出精確到小數點後兩位的 AC 代碼。

幾何建模

向量 OA = (x1, y1), OB = (x2, y2)。夾角 θ 滿足：

cos θ = (OA · OB) / (|OA| |OB|)
      = (x1*x2 + y1*y2) / (√(x1²+y1²) √(x2²+y2²))

為避免大數平方溢出/精度損失，用餘弦定理等價形式：

c² = a² + b² - 2ab cos θ
cos θ = (a² + b² - c²) / (2ab)

其中：

• a² = x1² + y1² = |OA|²
• b² = x2² + y2² = |OB|²
• c² = (x1-x2)² + (y1-y2)² = |AB|²

代碼實現（C）

#include <stdio.h>
#include <math.h>

const double PI = acos(-1.0);

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        double x1, y1, x2, y2;
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        double a2 = x1*x1 + y1*y1;
        double b2 = x2*x2 + y2*y2;
        double c2 = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
        double cos_theta = (a2 + b2 - c2) / (2 * sqrt(a2 * b2));
        // 數值誤差修正：限制在 [-1, 1]
        if (cos_theta > 1) cos_theta = 1;
        if (cos_theta < -1) cos_theta = -1;
        double angle = acos(cos_theta) * 180.0 / PI;
        printf("%.2lf\n", angle);
    }
    return 0;
}

關鍵細節

1. 雙精度：座標絕對值 ≤ 10000，平方和 ≤ 2×10⁸，double 足夠精確。
2. acos 定義域保護：浮點誤差可能導致 cos_theta 略超出 [-1,1]，必須 clamp。
3. 角度制轉換：rad * 180 / PI。
4. 輸出格式：%.2lf 保留兩位小數，四捨五入。

複雜度

• 每測試用例 O(1)
• 總時間 O(T)，極快

總結

本題是平面向量夾角的直接應用。關鍵在於選擇數值穩定的公式（餘弦定理避免了點積分子分母分別開根），並處理浮點邊界誤差。掌握「向量夾角 = acos(點積/模積)」與「餘弦定理」兩種等價形式，可靈活應對不同數值範圍的問題。