1. 题目

传送门=￣ω￣=

双倍经验：SPOJ-CIRU（记得把精度 $eps$调成 $10^{-7}$）

2. 题解

自适应 Simpson 积分板题

然而其实这题卡辛普森积分。。。

$eps$需要开到 $10^{-13}$。。。

惊了.jpg

所以此题需要卡卡常，直接搞很难过.avi

（我最后是 19s 过的，最后一秒献给虵）

#include <bits/stdc++.h>

#define NS (1005)
#define FIR first
#define SEC second
#define eps (1e-13)
#define POW2(a) ((a) * (a))

using namespace std;

typedef pair<double, bool> PDB;

struct Circle
{
    double x, y, r;
    bool operator < (const Circle oth) const {return r < oth.r;}
} cir[NS];

int n;

inline double F(double x)
{
    static PDB tmp[NS << 1]; double q, res = 0; int cnt = 0;
    for (int i = 1; i <= n; i += 1) if (cir[i].r > fabs(cir[i].x - x))
    {
        q = sqrt(POW2(cir[i].r) - POW2(cir[i].x - x));
        tmp[++cnt].FIR = cir[i].y - q, tmp[cnt].SEC = 1;
        tmp[++cnt].FIR = cir[i].y + q, tmp[cnt].SEC = 0;
    }
    sort(tmp + 1, tmp + 1 + cnt); int f = 0;
    for (int i = 1; i <= cnt; i += 1)
        if (tmp[i].SEC) {if (!(f++)) q = tmp[i].FIR;}
        else if (!(--f)) res += tmp[i].FIR - q;
    return res;
}

inline double cal(double l, double r, double fl, double fr, double fm)
{
    return (r - l) * (fl + fr + 4 * fm) / 6;
}

double sps(double l, double r, double fl, double fr, double fm)
{
    double m = (l + r) / 2, flm = F((l + m) / 2), frm = F((m + r) / 2);
    double dt = cal(l, r, fl, fr, fm);
    dt -= cal(l, m, fl, fm, flm) + cal(m, r, fm, fr, frm);
    if (abs(dt) < eps) return cal(l, r, fl, fr, fm);
    return sps(l, m, fl, fm, flm) + sps(m, r, fm, fr, frm);
}

inline double DIS(int a, int b)
{
    return sqrt(POW2(cir[a].x - cir[b].x) + POW2(cir[a].y - cir[b].y));
}

bool book[NS];

int main(int argc, char const* argv[])
{
    scanf("%d", &n); double l = 2e33, r = -2e33;
    for (int i = 1; i <= n; i += 1)
    {
        scanf("%lf%lf%lf", &cir[i].x, &cir[i].y, &cir[i].r);
        l = min(l, cir[i].x - cir[i].r), r = max(r, cir[i].x + cir[i].r);
    }
    sort(cir + 1, cir + 1 + n);
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = i + 1; j <= n; j += 1)
            if (DIS(i, j) + cir[i].r <= cir[j].r)
            {book[i] = 1; goto nxt;}
        nxt : continue;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i += 1) if (!book[i]) cir[++cnt] = cir[i];
    n = cnt, printf("%.3f", sps(l, r, F(l), F(r), F((l + r) / 2)));
    return 0;
}

上面那个代码能被这个数据卡掉：

3
0 0 1
0 0 1
100 100 1

然后我就写了下面这个代码，本机 AC 提交瞬间（4ms）WA。。。反正也不是很清楚是为什么，反正并不是很重要，毕竟 BZOJ 嘛。。。

当然这个代码在 SPOJ 上是能 AC 的。。。

#include <bits/stdc++.h>

#define NS (1005)
#define FIR first
#define SEC second
#define eps (1e-13)
#define POW2(a) ((a) * (a))
#define REG register

using namespace std;

typedef pair<double, bool> PDB;

struct Circle
{
    double x, y, r;
    bool operator < (const Circle oth) const {return r < oth.r;}
} cir[NS];

int n;

inline double F(double x)
{
    static PDB tmp[NS << 1]; REG double q, res = 0; REG int cnt = 0;
    for (REG int i = 1; i <= n; i += 1) if (cir[i].r > fabs(cir[i].x - x))
    {
        q = sqrt(POW2(cir[i].r) - POW2(cir[i].x - x));
        tmp[++cnt].FIR = cir[i].y - q, tmp[cnt].SEC = 1;
        tmp[++cnt].FIR = cir[i].y + q, tmp[cnt].SEC = 0;
    }
    sort(tmp + 1, tmp + 1 + cnt); REG int f = 0;
    for (REG int i = 1; i <= cnt; i += 1)
        if (tmp[i].SEC) {if (!(f++)) q = tmp[i].FIR;}
        else if (!(--f)) res += tmp[i].FIR - q;
    return res;
}

inline double cal(double l, double r, double fl, double fr, double fm)
{
    return (r - l) * (fl + fr + 4 * fm) / 6;
}

double sps(double l, double r, double fl, double fr, double fm)
{
    REG double m = (l + r) / 2, flm = F((l + m) / 2), frm = F((m + r) / 2);
    REG double dt = cal(l, r, fl, fr, fm);
    dt -= cal(l, m, fl, fm, flm) + cal(m, r, fm, fr, frm);
    if (abs(dt) < eps) return cal(l, r, fl, fr, fm);
    return sps(l, m, fl, fm, flm) + sps(m, r, fm, fr, frm);
}

inline double DIS(REG int a, REG int b)
{
    return sqrt(POW2(cir[a].x - cir[b].x) + POW2(cir[a].y - cir[b].y));
}

bool book[NS];

PDB h[NS << 1];

int main(int argc, char const* argv[])
{
    scanf("%d", &n); REG double ans = 0, q;
    for (REG int i = 1; i <= n; i += 1)
        scanf("%lf%lf%lf", &cir[i].x, &cir[i].y, &cir[i].r);
    sort(cir + 1, cir + 1 + n);
    for (REG int i = 1; i <= n; i += 1)
    {
        for (REG int j = i + 1; j <= n; j += 1)
            if (DIS(i, j) + cir[i].r <= cir[j].r)
            {book[i] = 1; goto nxt;}
        nxt : continue;
    }
    REG int cnt = 0;
    for (REG int i = 1; i <= n; i += 1) if (!book[i]) cir[++cnt] = cir[i];
    n = cnt, cnt = 0;
    for (REG int i = 1; i <= n; i += 1)
    {
        h[++cnt].FIR = cir[i].x - cir[i].r, h[cnt].SEC = 1;
        h[++cnt].FIR = cir[i].x + cir[i].r, h[cnt].SEC = 0;
    }
    sort(h + 1, h + 1 + cnt); REG int f = 0;
    for (REG int i = 1; i <= cnt; i += 1)
        if (h[i].SEC) {if (!(f++)) q = h[i].FIR;}
        else if (!(--f))
            ans += sps(q, h[i].FIR, F(q), F(h[i].FIR), F((q + h[i].FIR) / 2));
    printf("%.3f\n", ans);
    return 0;
}