您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 2892 Area：多邊形與圓相交面積計算幾何題解

編輯：C++ 入門

題目大意

給定一個多邊形（島嶼）和一個圓（炸彈爆炸範圍），求兩者相交的面積。多邊形頂點數 n ≤ 100,000，圓心座標與半徑由物理公式計算得出。

解題思路：分解為三角形與圓的相交

以圓心為頂點，將多邊形劃分為 n 個三角形（第 i 個三角形由圓心、頂點 i、頂點 i+1 構成）。總相交面積即為所有三角形與圓相交面積之和（注意有向面積，需根據叉積符號決定正負）。

三角形與圓相交的分類討論

設三角形兩頂點為 A、B，圓心 O，半徑 r。根據 A、B 相對於圓的位置：

兩點都在圓內：相交面積 = 三角形面積 |cross(OA, OB)| / 2。
一點在內、一點在外：相交面積 = 小三角形面積 + 扇形面積。需求出線段 AB 與圓的交點 T，分別計算三角形 OAT 或 OBT 面積與扇形面積。
兩點都在圓外：
- 線段 AB 與圓無交點或 1 個交點（相切）：相交面積 = 扇形面積 r² * angle(A, B) / 2。
- 線段 AB 與圓有 2 個交點 P、Q：相交面積 = 大扇形面積 + 小三角形面積 - 小扇形面積 = r² * angle(A, B)/2 + |cross(OP, OQ)|/2 - r² * angle(P, Q)/2。

關鍵幾何工具函數

// 向量運算
typedef Point Vector;
Vector operator+(Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator-(Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator*(Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator/(Vector A, double p) { return Vector(A.x/p, A.y/p); }

double dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double length(Vector A) { return sqrt(dot(A, A)); }
double cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
double angle(Vector A, Vector B) { return acos(dot(A, B) / length(A) / length(B)); }

// 點到直線距離
double point_line_distance(Point P, Point A, Point B) {
    Vector AP = P - A, AB = B - A;
    return fabs(cross(AP, AB) / length(AB));
}

// 直線與圓交點（返回交點數 0/1/2，交點存入 v）
int circle_line_intersect(Circle C, Point A, Point B, vector<Point> &v) {
    double dist = point_line_distance(C.c, A, B);
    int d = dcmp(dist - C.r);
    if (d > 0) return 0;
    Point pro = point_line_projection(C.c, A, B);
    if (d == 0) { v.push_back(pro); return 1; }
    double len = sqrt(C.r*C.r - dist*dist);
    Vector AB = B - A;
    Vector l = AB / length(AB) * len;
    v.push_back(pro + l);
    v.push_back(pro - l);
    return 2;
}

核心計算函數

double circle_delta_intersect_area(Circle C, Point A, Point B) {
    Vector CA = A - C.c, CB = B - C.c;
    double da = length(CA), db = length(CB);
    da = dcmp(da - C.r); db = dcmp(db - C.r);

    if (da <= 0 && db <= 0) return fabs(cross(CA, CB)) * 0.5; // 兩點在圓內

    vector<Point> v;
    int num = circle_line_intersect(C, A, B, v);
    double carea = C.r * C.r * PI;

    if (da <= 0 && db > 0) { // A 內 B 外
        Point t = point_on_segment(v[0], A, B) ? v[0] : v[1];
        double area = fabs(cross(CA, t - C.c)) * 0.5;
        double an = angle(CB, t - C.c);
        return area + carea * an / PI / 2;
    }
    if (da > 0 && db <= 0) { // A 外 B 內
        Point t = point_on_segment(v[0], A, B) ? v[0] : v[1];
        double area = fabs(cross(CB, t - C.c)) * 0.5;
        double an = angle(CA, t - C.c);
        return area + carea * an / PI / 2;
    }
    // 兩點都在圓外
    if (num == 2) {
        double bigarea = carea * angle(CA, CB) / PI / 2;
        double smallarea = carea * angle(v[0]-C.c, v[1]-C.c) / PI / 2;
        double deltaarea = fabs(cross(v[0]-C.c, v[1]-C.c)) * 0.5;
        return bigarea + deltaarea - smallarea;
    }
    return carea * angle(CA, CB) / PI / 2; // 相切或無交點
}

主流程

double circle_polygon_intersect_area() {
    p[n] = p[0]; // 閉合
    double ans = 0;
    for (int i = 0; i < n; i++) {
        double area = circle_delta_intersect_area(bomb, p[i], p[i+1]);
        if (cross(p[i]-bomb.c, p[i+1]-bomb.c) < 0) area = -area; // 有向面積
        ans += area;
    }
    return ans > 0 ? ans : -ans;
}