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

UVA 11722 概率幾何：隨機線段與矩形相交面積比期望值

編輯：關於C++

題目大意

給定矩形 [t1, t2] × [s1, s2] 和帶寬 w 的對角帶區域：|y - x| ≤ w (即兩條平行線 y = x + w 和 y = x - w 之間)。
在矩形中均勻隨機取點 (x, y)，求點落在帶區域內的概率 (即相交面積 / 矩形面積)。

幾何分析：面積計算

矩形面積 A = (t2-t1)(s2-s1)。
帶區域由兩條線 L1: y = x + w、L2: y = x - w 夾成。
相交區域為凸多邊形 (通常為六邊形、四邊形或三角形)。

通用方法：多邊形面積 = 三角形面積和

求矩形四頂點
求兩條線與矩形四邊的交點 (共 ≤ 8 個)
收集所有在矩形內的交點 + 矩形內部的頂點
凸包排序 (或極角排序) 得到多邊形頂點序列
三角剖分求面積：Area = Σ cross(p[i]-p[0], p[i+1]-p[0]) / 2

簡化解法：直接幾何情況討論

因線條斜率固定為 1，可直接推導面積公式。但為通用性，代碼採用線段-直線相交 + 多邊形面積模板。

核心幾何模板

struct Point { double x, y; };
using Vector = Point;

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

// 線段 p1-p2 與直線 p3-p4 (方向 v) 相交判斷
bool segLineIntersect(Point p1, Point p2, Point p3, Vector v) {
    double d1 = cross(v, p1 - p3);
    double d2 = cross(v, p2 - p3);
    return d1 * d2 <= 0; // 異號或零
}

// 直線 p1+tv1 和 p2+tv2 求交點
Point lineLineIntersect(Point p1, Vector v1, Point p2, Vector v2) {
    Vector u = p2 - p1;
    double t = cross(u, v2) / cross(v1, v2);
    return {p1.x + v1.x * t, p1.y + v1.y * t};
}

// 三角形面積
double triangleArea(Point a, Point b, Point c) {
    return fabs(cross(b-a, c-a)) / 2;
}

完整解題邏輯

double solve(double t1, double t2, double s1, double s2, double w) {
    // 矩形四頂點
    Point p1 = {t1, s1}, p2 = {t2, s1}, p3 = {t2, s2}, p4 = {t1, s2};
    double rectArea = (t2-t1) * (s2-s1);

    // 兩條邊界線
    Line L1 = {{0, w}, {1, 1}};   // y = x + w
    Line L2 = {{0, -w}, {1, 1}};  // y = x - w

    // 矩形四邊
    Segment segs[4] = {{p1,p2}, {p2,p3}, {p3,p4}, {p4,p1}};

    vector poly;
    // 1. 矩形內部的頂點
    if (p1.y >= p1.x - w && p1.y <= p1.x + w) poly.push_back(p1);
    if (p2.y >= p2.x - w && p2.y <= p2.x + w) poly.push_back(p2);
    if (p3.y >= p3.x - w && p3.y <= p3.x + w) poly.push_back(p3);
    if (p4.y >= p4.x - w && p4.y <= p4.x + w) poly.push_back(p4);

    // 2. 邊界線與矩形邊的交點
    for (auto& seg : segs) {
        if (segLineIntersect(seg.a, seg.b, L1.p, L1.v)) {
            poly.push_back(lineLineIntersect(L1.p, L1.v, seg.a, seg.b - seg.a));
        }
        if (segLineIntersect(seg.a, seg.b, L2.p, L2.v)) {
            poly.push_back(lineLineIntersect(L2.p, L2.v, seg.a, seg.b - seg.a));
        }
    }

    // 3. 凸包/極角排序
    Point center = {0,0};
    for (auto& p : poly) { center.x += p.x; center.y += p.y; }
    center.x /= poly.size(); center.y /= poly.size();
    sort(poly.begin(), poly.end(), [&](Point a, Point b) {
        return atan2(a.y-center.y, a.x-center.x) < atan2(b.y-center.y, b.x-center.x);
    });

    // 4. 三角剖分求面積
    double area = 0;
    for (int i = 1; i+1 < poly.size(); ++i)
        area += triangleArea(poly[0], poly[i], poly[i+1]);

    return area / rectArea;
}