HDU 2528 Area：多邊形被直線分割面積計算

問題描述

給定凸多邊形（或一般簡單多邏形）頂點坐標（按序），及一條直線。直線保證將多邊形分成兩部分。求兩部分面積（大面積在前）。

解題思路

1. 計算多邊形總面積 S（叉積公式）
2. 遍歷每條邊，判斷與直線是否相交
3. 找到第一個交點 P，從該邊的下一個頂點開始累加面積（叉積），直到第二個交點 Q
4. 累加面積包括：P → 頂點們 → Q → P 形成的多邏形面積
5. 另一部分面積 = S - 面積1

關鍵幾何運算

• 向量叉積：cross(a, b) = a.x*b.y - a.y*b.x
• 三角形面積：|cross(b-a, c-a)| / 2
• 多邊形面積：|Σ cross(p[i]-p[0], p[i+1]-p[0])| / 2
• 直線與線段相交判斷：兩端點在直線兩側（叉積異號）或一端點在線上
• 求交點：參數方程法

參考代碼（C++）

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

const int MAXN = 30;
const double EPS = 1e-8;

int dcmp(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); }

struct Point { double x, y; };
typedef Point Vector;

Vector operator+(Vector a, Vector b) { return {a.x+b.x, a.y+b.y}; }
Vector operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
Vector operator*(Vector a, double k) { return {a.x*k, a.y*k}; }
double cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }

int n; Point p[MAXN]; struct Line { Point a, b; } L;

bool seg_line_intersect(Line L, Point A, Point B, Point &P) {
    Vector v1 = A - L.b, v2 = L.a - L.b, v3 = B - L.b;
    if (dcmp(cross(v1, v2)) * dcmp(cross(v2, v3)) >= 0) {
        Vector u = L.a - A;
        double t = cross(A - B, u) / cross(v2, A - B);
        P = L.a + v2 * t;
        return true;
    }
    return false;
}

double polygon_area() {
    double s = 0;
    for (int i = 1; i < n-1; i++) s += cross(p[i]-p[0], p[i+1]-p[0]);
    return fabs(s) * 0.5;
}

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
        scanf("%lf%lf%lf%lf", &L.a.x, &L.a.y, &L.b.x, &L.b.y);
        double total = polygon_area();
        p[n] = p[0];
        double part = 0;
        Point P, Q;
        int state = 0;
        for (int i = 0; i < n; i++) {
            if (state == 0 && seg_line_intersect(L, p[i], p[i+1], P)) {
                part += cross(P, p[i+1]);
                state = 1;
            } else if (state == 1 && seg_line_intersect(L, p[i], p[i+1], Q) && dcmp(P.x-Q.x) || dcmp(P.y-Q.y)) {
                part += cross(p[i], Q);
                part += cross(Q, P);
                state = 2;
                break;
            } else if (state == 1) {
                part += cross(p[i], p[i+1]);
            }
        }
        part = fabs(part) * 0.5;
        double other = total - part;
        if (part < other) swap(part, other);
        printf("%.0lf %.0lf\n", part, other);
    }
    return 0;
}

複雜度

• 時間：O(n)，單次遍歷邊
• 空間：O(n)

注意點

1. 交點可能在頂點上，需去重（代碼中 P != Q 判斷）
2. 面積公式需取絕對值
3. 輸出四捨五入到整數（%.0lf）