圆类

Circle getCircle(pt A, pt B, pt C)
三点确定一个圆
Circle minCover(vector<pt> &p)
求点集 p 的最小圆覆盖
db SPICA(Circle C, vector<pt> &p)
求圆 C 和多边形 p 的面积交

struct Circle {
    pt o; db r;
    Circle() {}
    Circle(pt o, db r) : o(o), r(r) {}
    Circle(db x, db y, db r) : o(pt(x, y)), r(r) {}
    db area() {
        return pi * r * r;
    }
};

Circle getCircle(pt A, pt B, pt C) {
    pt p1 = (A + B) / 2.0, p2 = (B + C) / 2.0;
    pt p3 = rotate_point(A - p1, pi / 2) + p1;
    pt p4 = rotate_point(C - p2, pi / 2) + p2;
    pt o; line_make_pt(line(p1, p3), line(p2, p4), o);
    return Circle(o, (o - A).norm());
}

Circle minCover(vector<pt> &p) {
    size_t n = p.size();
    auto shuffle = [&](vector<pt> &v) {
        for (int i = 1; i < n; i++) {
            swap(v[i], v[rand() % n]);
        }
    };
    auto PIC = [&](Circle &C, pt &p) -> bool {
        return cmp((p - C.o).norm() - C.r) <= 0;
    };
    shuffle(p);
    Circle C = Circle(p[0], 0);
    for (int i = 1; i < n; i++) if (!PIC(C, p[i])) {
        C = Circle(p[i], 0);
        for (int j = 0; j < i; j++) if (!PIC(C, p[j])) {
            C.o = (p[i] + p[j]) * 0.5;
            C.r = (p[j] - C.o).norm();
            for (int k = 0; k < j; k++) if (!PIC(C, p[k])) {
                C = getCircle(p[i], p[j], p[k]);
            }
        }
    }
    return C;
}

db LineCrossCircle(const line &l, const Circle &C, pt &p1, pt &p2) {
    pt a = l.a, b = l.b;
    pt r = C.o; db R = C.r;
    pt fp;
    line_make_pt(line(r, pt(r.x + a.y - b.y, r.y + b.x - a.x)), l, fp);
    db rtol = dis(r, fp), atob = dis(a, b);
    db rtos = pt_on_seg(fp, a, b) ? rtol : min(dis(r, a), dis(r, b));
    db fptoe = sqrt(sqr(R) - sqr(rtol)) / atob;
    if (cmp(R - rtos) <= 0) return rtos;
    p1 = fp + (a - b) * fptoe;
    p2 = fp + (b - a) * fptoe;
    return rtos;
}

db SectorArea(const pt &o, const pt &a, const pt &b, double R) {
//不大于180度扇形面积，o->a->b逆时针
    db A2 = sqr(dis(o, a)), B2 = sqr(dis(o, b)), C2 = sqr(dis(a, b));
    return sqr(R) * acos((A2 + B2 - C2) / 2 / sqrt(A2) / sqrt(B2)) / 2;
}

double TACIA(Circle &C, pt &a, pt &b) {
// TriangleAndCircleIntersectArea，逆时针，r为圆心
    pt r = C.o; db R = C.r;
    db adis = dis(r, a), bdis = dis(r, b);
    if (cmp(adis - R) <= 0 && cmp(bdis - R) <= 0) {
        return det(a - r, b - r) / 2;
    }
    pt ta, tb;
    if (pt_on_seg(r, a, b)) return 0.0;
    db rtos = LineCrossCircle(line(a, b), Circle(r, R), ta, tb);
    if (cmp(rtos - R) >= 0) return SectorArea(r, a, b, R);
    db S1 = SectorArea(r, tb, b, R), S2 = SectorArea(r, a, ta, R);
    if (cmp(adis - R) <= 0) return det(a - r, tb - r) / 2 + S1;
    if (cmp(bdis - R) <= 0) return det(ta - r, b - r) / 2 + S2;
    return det(ta - r, tb - r) / 2 + S2 + S1;
}


db SPICA(Circle C, vector<pt> &p) {
// SimplePolygonIntersectCircleArea
    size_t n = p.size();
    db res = 0;
    for (int i = 0; i < n; i++) {
        int flag = cmp(det(p[i] - C.o, p[nex(i)] - C.o));
        if (flag < 0) res -= TACIA(C, p[nex(i)], p[i]);
        else res += TACIA(C, p[i], p[nex(i)]);
    }
    return fabs(res);
}

int main(int argc, const char * argv[]) {
    int n; db r;
    while (~scanf("%lf", &r)) {
        scanf("%d", &n);
        vector<pt> p(n);
        for (int i = 0; i < n; i++) p[i].input();
        printf("%.2f\n", SPICA(Circle(0, 0, r), p));
    }
    return 0;
}

圆的面积并

SP8073 CIRU

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 1005;
const db eps = 1e-5;
typedef db func(db);
int n;

struct Circle {
    db x, y, r;
    bool operator < (const Circle &a) const {
        return r < a.r;
    }
}c[N];

struct Line {
    db l, r;
    bool operator < (const Line &a) const {
        return l < a.l;
    }
}seg[N];

db sqr(db x) {
    return x * x;
}

map<db, db> ma;
db f(db x) {
    if (ma[x]) return ma[x];
    static Line l[N]; int tot = 0;
    for (int i = 1; i <= n; i++) {
        db delta = sqr(c[i].r) - sqr(c[i].x - x);
        if (delta < eps) continue;
        delta = sqrt(delta);
        l[++tot] = Line{c[i].y - delta, c[i].y + delta};
    }
    sort(l + 1, l + 1 + tot);
    db res = 0, lst = -1e9;
    for (int i = 1; i <= tot; i++) {
        const Line &now = l[i];
        if (now.l > lst) {
            res += now.r - now.l; lst = now.r;
        }
        else if (now.r > lst) {
            res += now.r - lst; lst = now.r;
        }
    }
    return ma[x] = res;
}

db simpson(db l, db r, func f) {
    db mid = (l + r) / 2;
    return (f(l) + 4 * f(mid) + f(r)) * (r - l) / 6;
}
db asr(db l, db r, db eps, db A, func f) {
    db mid = (l + r) / 2;
    db L = simpson(l, mid, f), R = simpson(mid, r, f);
    if (fabs(L + R - A) <= 15 * eps) return L + R + (L + R - A) / 15;
    return asr(l, mid, eps / 2, L, f) + asr(mid, r, eps / 2, R, f);
}
db asr(db l, db r, db eps, func f) {
    return asr(l, r, eps, simpson(l, r, f), f);
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    db l = 1e15, r = -1e15;
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf", &c[i].x, &c[i].y, &c[i].r);
        l = min(l, c[i].x - c[i].r);
        r = max(r, c[i].x + c[i].r);
    }

    sort(c + 1, c + 1 + n);
    int tmp = 0;
    for (int i = 1; i <= n; i++) {
        int flag = 1;
        for (int j = i + 1; j <= n; j++) {
            if (sqr(c[i].x - c[j].x) + sqr(c[i].y - c[j].y) <= sqr(c[j].r - c[i].r)) {
                flag = 0; break;
            }
        }
        if (flag) c[++tmp] = c[i];
    }
    n = tmp;

    for (int i = 1; i <= n; i++) {
        seg[i] = Line{c[i].x - c[i].r, c[i].x + c[i].r};
    }
    sort(seg + 1, seg + 1 + n);
    db res = 0, lst = -1e9;
    for (int i = 1; i <= n; i++) {
        const Line &now = seg[i];
        if (now.l > lst) {
            res += asr(now.l, now.r, eps, f); lst = now.r;
        }
        else if (now.r > lst) {
            res += asr(lst, now.r, eps, f); lst = now.r;
        }
    }
    printf("%.3f\n", res);
    return 0;
}