# 2. 题解

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

（我最后是 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


#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;
}