三角形面积并问题

解题思路：

本题要求若干个三角形的面积并。一般求图形的面积并可以尝试用扫描线来做。

用扫描线来做的话，首先要将整个平面根据所有点的横坐标划分成若干个长条区间，保证每个区间内部不存在点。但是本题是若干个三角形，三角形不同于矩形，如果矩形之间存在交点，那么这些交点一定和某一个矩形的顶点在同一个区间的边界上。但是三角形就不一定了，三角形与三角形之间的交点并不一定和某个三角形的顶点在同一个区间的边界上。

因此如果我们要想保证每个区间内部不存在点，我们需要将所有交点也考虑进来，要将整个平面根据所有顶点和交点划分成若干个长条区间。

然后我们对于每个长条区间，求一下该区间内部的所有三角形的面积并。由于此时所有顶点和交点都一定在区间的边界上，因此此时每个区间内部一定不存在交点，因此区间内部一定会有很多条边（如果当前区间没边直接不用考虑），并且所有边之间一定不存在交集（最多在边界上相交），而且由于三角形是封闭图形，所以所有边一定是成对出现的。因此如果把三角形也看作一个特殊的梯形，那么每个区间中一定是若干个梯形加在一起。

然后对于每个梯形，可以用梯形公式来求面积，只需要求出每个梯形的上底和下底即可，然后由于每个区间中所有梯形的高都是相同的，因此所有梯形的面积就可以统一的用上底的和加上下底的和再乘高除以 $2$ 就是所有梯形的和。而上底的和就是所有三角形在当前区间的左边界上的交集的长度，下底的和就是所有三角形在当前区间的右边界上交集的长度。

因此，我们其实只需要对于每个区间，求一下它左边界上所有三角形的交集的总长度，和右边界上的所有三角形的交集的总长度，就能计算出每个区间的梯形面积，所有区间的梯形面积加在一起，就是所有三角形的面积并。

对于边界上所有三角形的交集的总长度，我们将每个三角形在边界上的部分看作一个区间，则所有三角形在边界上的长度就是所有区间的交集，我们只需要对这些区间做一下区间合并，就能得到所有三角形在边界上的交集了。

由于任意两个三角形之间都可能存在交点，因此划分区间的数量最坏可能是 $O(n^2)$ 级别的，然后每个区间内部最多会有 $n$ 个三角形，还需要进行排序，因此整个算法的时间复杂度是 $O(n^3logn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 110;
const double eps = 1e-8;
const double INF = 1e6;

int n;
PDD tr[N][3]; //存储每个三角形的坐标
vector<double> xs; //存储所有点的横坐标
PDD q[N]; //记录当前线段上的所有区间

int sign(double x) //符号函数
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(double x, double y) //比较函数
{
    if(abs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

PDD operator+(PDD a, PDD b) //重载向量加法
{
    return {a.x + b.x, a.y + b.y};
}

PDD operator-(PDD a, PDD b) //重载向量减法
{
    return {a.x - b.x, a.y - b.y};
}

PDD operator*(PDD a, double t) //重载数乘
{
    return {a.x * t, a.y * t};
}

double operator*(PDD a, PDD b) //重载叉积
{
    return a.x * b.y - a.y * b.x;
}

double operator&(PDD a, PDD b) //重载点积
{
    return a.x * b.x + a.y * b.y;
}

bool on_segment(PDD p, PDD a, PDD b) //判断 p 是否在线段 ab 上
{
    return sign((p - a) & (p - b)) <= 0;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) //求两个点向式直线的交点
{
    if(!sign(v * w)) return {INF, INF}; //如果两条直线平行，则不存在交点
    PDD u = p - q;
    double t = (w * u) / (v * w);
    PDD o = p + v * t;
    //如果交点不在两条直线上，也说明不存在交点
    if(!on_segment(o, p, p + v) || !on_segment(o, q, q + w)) return {INF, INF};
    return o;
}

double line_area(double a, int side) //求边界 a 右边的三角形和边界 a 的交集长度
{
    int cnt = 0; //记录线段上区间个数
    for(int i = 0; i < n; i++)
    {
        auto t = tr[i];
        if(dcmp(t[0].x, a) > 0 || dcmp(t[2].x, a) < 0) continue;
        if(!dcmp(t[0].x, a) && !dcmp(t[1].x, a)) //如果 a 右边的三角形和边界 a 重合，单独处理
        {
            if(side) q[cnt++] = {t[0].y, t[1].y}; //这种情况只有边界 a 和右边三角形的交集才需要算
        }
        else if(!dcmp(t[2].x, a) && !dcmp(t[1].x, a)) //如果 a 左边的三角形和边界 a 重合，单独处理
        {
            if(!side) q[cnt++] = {t[2].y, t[1].y}; //这种情况只有边界 a 和左边三角形的交集才需要算
        }
        else //否则说明是一般情况，统一处理
        {
            double d[3];
            int u = 0;
            for(int j = 0; j < 3; j++)
            {
                PDD o = get_line_intersection(t[j], t[(j + 1) % 3] - t[j], {a, -INF}, {0, INF * 2}); 
                if(dcmp(o.x, INF)) //如果存在交点
                    d[u++] = o.y;
            }
            if(u) //如果存在交点，则至少两个，最多三个，此时所有交点的纵坐标最小值到纵坐标最大值就是区间
            {
                sort(d, d + u);
                q[cnt++] = {d[0], d[u - 1]};
            }
        }
    }
    if(!cnt) return 0; //如果线段上不存在区间，直接返回 0
    for(int i = 0; i < cnt; i++)
        if(q[i].x > q[i].y)
            swap(q[i].x, q[i].y); //保证区间左端点更小
    sort(q, q + cnt); //将所有区间从小到大排序
    double res = 0, st = q[0].x, ed = q[0].y;
    for(int i = 1; i < cnt; i++)
        if(q[i].x <= ed) ed = max(ed, q[i].y); //区间合并
        else
        {
            res += ed - st; //累加每个合并后区间的长度
            st = q[i].x, ed = q[i].y;
        }
    res += ed - st; //累加最后一个合并后区间的长度
    return res;
}

double range_area(double a, double b) //求区间 [a, b] 中的面积
{
    return (line_area(a, 1) + line_area(b, 0)) * (b - a) / 2;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            scanf("%lf%lf", &tr[i][j].x, &tr[i][j].y);
            xs.push_back(tr[i][j].x);
        }
        sort(tr[i], tr[i] + 3); //将每个三角形的三个顶点按照横坐标排序，方便判断三角形和某个区间是否有交集
    }

    //求所有三角形之间的交点
    for(int i = 0; i < n; i++) //枚举第一个三角形
        for(int j = i + 1; j < n; j++) //枚举第二个三角形
            for(int x = 0; x < 3; x++) //枚举第一个三角形的边
                for(int y = 0; y < 3; y++) //枚举第二个三角形的边
                {
                    PDD o = get_line_intersection(tr[i][x], tr[i][(x + 1) % 3] - tr[i][x],
                                                  tr[j][y], tr[j][(y + 1) % 3] - tr[j][y]);
                    if(dcmp(o.x, INF)) xs.push_back(o.x); //如果当前两条边存在交点，将交点的横坐标存下来
                }

    //将所有横坐标排序
    sort(xs.begin(), xs.end());

    double res = 0; //记录答案
    for(int i = 0; i + 1 < xs.size(); i++)
        if(dcmp(xs[i], xs[i + 1])) //如果当前区间宽度不为 0，计算当前区间内的面积
            res += range_area(xs[i], xs[i + 1]); //累加当前区间的面积
    printf("%.2lf\n", res);

    return 0;
}