圆的面积并问题

解题思路：

本题要求若干个圆的面积并，求图形的面积并常用的做法就是扫描线。

这里区别于普通的扫描线做法，因为如果用常规的扫描线的做法，每个区间中圆弧的面积并很难求。

我们这里需要用自适应辛普森积分来求圆的面积并，同样用类似积分的思想来考虑。假设平面上有无数条竖线。每条竖线和所有圆都存在一个交集，如果竖线足够多，那么将所有竖线和圆的交集的面积加在一起，从积分的角度来看，这就能近似成所有圆的面积并了。

我们定义 $f(x_0)$ 表示 $x=x_0$ 这条竖线和所有圆的交集的长度。那么所有圆的面积并就可以看成是在 $(-\infty,+\infty)$ 区间内 $f(x)$ 的积分，而所有圆的坐标最多只会从 $-2000 \sim 2000$，并不是真的 $\infty$。这样我们每次求的交集部分都能近似看成一条线段，就可以用圆心搭配勾股定理直接求了，而如果用普通的扫描线的做法，每次要求的去求区间内圆弧的交集，那就比较难做了。

注意，本题如果圆和圆隔得比较远，就可能出现近似面积与真实面积相差较大的情况，这种情况类似于高次函数。所以可以将所有圆所在的横坐标区间取出来，进行一次区间合并，然后对于每个存在圆的区间单独计算面积，加在一起就是答案。

可参考：自适应辛普森积分的相关概念

C++ 代码

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

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 1010;
const double eps = 1e-8;
const double INF = 1e20;

struct Circle
{
    PDD p; //圆心
    double r; //半径
}c[N]; //存储所有圆

int n;
PDD q[N]; //存储当前所有竖线上的区间
vector<PDD> segs; //存储所有包含圆的横坐标区间

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

double f(double x) //设 f(x0) 表示 x = x0 和所有圆的交集的长度
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        double X = fabs(x - c[i].p.x), R = c[i].r;
        if(dcmp(X, R) < 0) //如果第 i 个圆和 x = x0 有交集
        {
            double Y = sqrt(R * R - X * X);
            q[cnt++] = {c[i].p.y - Y, c[i].p.y + Y};
        }
    }
    if(!cnt) return 0; //如果没有交集，直接返回 0

    sort(q, q + cnt); //将所有区间从小到大排序
    double res = 0; //记录并集的长度
    double 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 simpson(double l, double r) //求 [l, r] 内的近似面积
{
    double mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}

double asr(double l, double r, double s) //自适应辛普森积分，s 表示 [l, r] 区间内的近似面积
{
    double mid = (l + r) / 2;
    double left = simpson(l, mid), right = simpson(mid, r); //计算左、右区间的近似面积
    if(fabs(left + right - s) < eps) return left + right; //如果误差足够小，直接返回
    return asr(l, mid, left) + asr(mid, r, right); //否则继续递归
}

void merge() //区间合并
{
    sort(segs.begin(), segs.end()); //将所有区间排序
    vector<PDD> res;
    double st = -INF, ed = -INF;
    for(int i = 0; i < segs.size(); i++)
    {
        if(dcmp(segs[i].x, ed) <= 0) ed = max(ed, segs[i].y); //区间合并
        else
        {
            if(dcmp(st, -INF)) res.push_back({st, ed});
            st = segs[i].x, ed = segs[i].y;
        }
    }
    res.push_back({st, ed});
    segs = res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%lf%lf%lf", &c[i].p.x, &c[i].p.y, &c[i].r);
        segs.push_back({c[i].p.x - c[i].r, c[i].p.x + c[i].r}); //将所有圆的横坐标区间存储起来
    }

    merge(); //将所有横坐标区间合并

    double res = 0; //记录面积并
    for(int i = 0; i < segs.size(); i++) res += asr(segs[i].x, segs[i].y, simpson(segs[i].x, segs[i].y));
    printf("%.3lf\n", res);
    return 0;
}