HDU 幾何專題：兩圓公共面積計算 (Tell me the area)

HDU 幾何專題：兩圓公共面積計算 (Tell me the area)

給定平面上兩圓的圓心座標 (x, y) 與半徑 r，求其重疊面積，保留三位小數。涵蓋內含、內切、相交、外切、外離五種位置關係。

幾何關係分類

1. 內含/內切：圓心距 d ≤ |r1 - r2|，公共面積為較小圓面積 π·min(r1,r2)²。
2. 外切/外離：d ≥ r1 + r2，公共面積為 0。
3. 相交：|r1 - r2| < d < r1 + r2，需計算兩圓弧形成的透鏡形面積。

相交面積推導

連接兩交點與圓心構成四邊形，可分解為兩個三角形。利用餘弦定理求夾角：

cos(α) = (r1² + d² - r2²) / (2·r1·d)
cos(β) = (r2² + d² - r1²) / (2·r2·d)

扇形面積：S1 = ½·α·r1², S2 = ½·β·r2²。
三角形面積 (海倫公式)：SΔ = √[p(p-r1)(p-r2)(p-d)]，其中 p = (r1+r2+d)/2。
四邊形面積 = 2·SΔ。
公共面積 = S1 + S2 - 2·SΔ。

C++ 實現

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

struct Circle { double x, y, r; };

double dist(Circle a, Circle b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int main() {
    Circle a, b;
    while (scanf("%lf%lf%lf%lf%lf%lf", &a.x,&a.y,&a.r,&b.x,&b.y,&b.r) != EOF) {
        double d = dist(a, b);
        double area;
        if (d <= fabs(a.r - b.r))           // 內含/內切
            area = acos(-1.0) * min(a.r, b.r) * min(a.r, b.r);
        else if (d >= a.r + b.r)            // 外切/外離
            area = 0.0;
        else {                              // 相交
            double p = (a.r + b.r + d) / 2.0;
            double sa = acos((a.r*a.r + d*d - b.r*b.r) / (2.0*a.r*d));
            double sb = acos((b.r*b.r + d*d - a.r*a.r) / (2.0*b.r*d));
            area = sa*a.r*a.r + sb*b.r*b.r - 2*sqrt(p*(p-a.r)*(p-b.r)*(p-d));
        }
        printf("%.3lf\n", area);
    }
    return 0;
}

精度與邊界處理

• 使用 acos(-1.0) 獲取高精度 π。
• fabs 處理半徑差絕對值。
• 輸出 %.3lf 保證四捨五入到小數點後三位。