csu1812

题意

求三角形和矩形交的面积。
分析

半平面交。把三角形的三条边当作直线去切割矩形，最后求切割后的多边形面积即可。
code

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

const double eps = 1e-8;

int sgn(double x) { // 误差

    if(fabs(x) < eps) return 0;

    return x < 0 ? -1 : 1;

}

struct P {

    double x, y;

    P() {}

    P(double x, double y) : x(x), y(y) {}

    P operator + (const P p) const {

        return P(x + p.x, y + p.y);

    }

    P operator - (const P p) const {

        return P(x - p.x, y - p.y);

    }

    P operator * (const double tt) const {

        return P(x * tt, y * tt);

    }

    P operator / (const double tt) const {

        return P(x / tt, y / tt);

    }

    bool operator < (const P &p) const { // 坐标排序规则

        return x < p.x || (x == p.x && y < p.y);

    }

    double dot(const P &p) const { // 点积

        return x * p.x + y * p.y;

    }

    double det(const P &p) const { // 叉积

        return x * p.y - y * p.x;

    }

};

P tri[4], rec[5];

P b[5], c[5];

double A, B, C;

int m;

double cross(P o, P p, P q) { // 向量 op 和　oq 的叉积

    return (p.x - o.x) * (q.y - o.y) - (q.x - o.x) * (p.y - o.y);

}

void init() { // 顺时针排序

    if(sgn(cross(tri[0], tri[1], tri[2])) < 0)

        reverse(tri, tri + 3);

}

// 得到直线 pq : A * x + B * y + C = 0

// f(x,y) = A * x + B * y + C

// f(x,y) < 0 表示点(x,y)在直线pq的左边(此时可把pq当做向量)

void getLine(P p, P q) {

    A = q.y - p.y;

    B = p.x - q.x;

    C = q.det(p);

}

// 直线 A * x + B * y + C = 0 与 直线 pq 的交点

P intersect(P p, P q) {

    double u = fabs(A * p.x + B * p.y + C);

    double v = fabs(A * q.x + B * q.y + C);

    return P((p.x * v + q.x * u) / (u + v), (p.y * v + q.y * u) / (u + v));

}

double cal(P p) {

    return sgn(A * p.x + B * p.y + C);

}

void cut() {

    int tmpm = 0;

    for (int i = 0; i < m; i++) {

        if (cal(b[i]) <= 0) { // 判断是否在多边形内，这里指点在直线A * x + B * y + C = 0的左边或直线上

            c[tmpm++] = b[i];

        } else { // 虽然不在多边形内，但是可能和多边形内的点组成的直线与多边形产生新的交点

            if (cal(b[(i - 1 + m) % m]) < 0) {

                c[tmpm++] = intersect(b[(i - 1 + m) % m], b[i]);

            }

            if (cal(b[i + 1]) < 0) {

                c[tmpm++] = intersect(b[i + 1], b[i]);

            }

        }

    }

    for (int i = 0; i < tmpm; i++)

        b[i] = c[i];

    b[tmpm] = c[0];

    m = tmpm;

}

void solve() {

    tri[3] = tri[0];

    rec[4] = rec[0];

    memcpy(b, rec, sizeof rec);

    m = 4;

    for(int i = 0; i < 3; i++) {

        getLine(tri[i], tri[i + 1]);

        cut();

    }

}

// 求多边形面积　（a[]为多边形的点　n为点的个数）

double polygon_area(P *a, int n) {

    a[n] = a[0];

    double area = 0;

    for(int i = 0; i < n; i++) {

        area += a[i].det(a[i + 1]);

    }

    return fabs(area) / 2;

}

int main() {

    double x1, y1, x2, y2, x3, y3, x4, y4;

    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4)) {

        tri[0] = P(x1, y1);

        tri[1] = P(x2, y1);

        tri[2] = P(x1, y2);

        init();

        rec[0] = P(x3, y3);

        rec[1] = P(x4, y3);

        rec[2] = P(x4, y4);

        rec[3] = P(x3, y4);

        solve();

        printf("%.8f\n", polygon_area(b, m));

    }

    return 0;

}
巴特西

csu1812

csu1812

题意

分析

code

最新文章

热门文章
