题解

我们把圆拆成两个圆弧，按照圆弧的左右端点排序来增加和删除

那么我们把圆弧按照纵坐标排序，一定是两两不相交的

我们新加入一个圆的时候，找上圆弧的前驱，如果前驱是一个上圆弧，那么这个上圆弧所在的圆就是半径最小且包含它的圆，如果前驱是一个下圆弧，那么包含这个下圆弧的圆就是包含当前圆的圆

然后构建出一棵树，记录一下每个节点的深度就可以了

我们其实可以通过更改外部变量更改set的计算方式

代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

db X;

struct Arc {

    db x,y,r,on;int id;

    friend bool operator < (const Arc &a,const Arc &b) {

	db ay = a.on * sqrt(a.r * a.r - (X - a.x) * (X - a.x)) + a.y;

	db by = b.on * sqrt(b.r * b.r - (X - b.x) * (X - b.x)) + b.y;

	if(ay != by) return ay > by;

	else return a.on > b.on;

    }

};

struct circle {

    int64 x,y,r;

}C[MAXN];

int N,fa[MAXN],tot,dep[MAXN];

vector<int> son[MAXN];

pii p[MAXN * 2];

multiset<Arc> S;

void Init() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) {

	read(C[i].x);read(C[i].y);read(C[i].r);

    }

    for(int i = 1 ; i <= N ; ++i) {

	p[++tot] = mp(C[i].x - C[i].r,i);

	p[++tot] = mp(C[i].x + C[i].r,i);

    }

    sort(p + 1,p + tot + 1);

}

void dfs(int u) {

    int s = son[u].size();

    for(int i = 0 ; i < s ; ++i) {

	dep[son[u][i]] = dep[u] + 1;

	dfs(son[u][i]);

    }

}

void Solve() {

    for(int i = 1 ; i <= tot ; ++i) {

	int t = p[i].se;

	X = p[i].fi;

	if(p[i].fi == C[t].x - C[t].r) {

	    multiset<Arc>::iterator k = S.insert((Arc){(db)C[t].x,(db)C[t].y,(db)C[t].r,1,t});

	    if(k != S.begin()) {

		--k;

		if((*k).on > 0) fa[t] = (*k).id;

		else fa[t] = fa[(*k).id];

	    }

	    S.insert((Arc){(db)C[t].x,(db)C[t].y,(db)C[t].r,-1,t});

	}

	else {

	    S.erase((Arc){(db)C[t].x,(db)C[t].y,(db)C[t].r,1,t});

	    S.erase((Arc){(db)C[t].x,(db)C[t].y,(db)C[t].r,-1,t});

	}

    }

    for(int i = 1 ; i <= N ; ++i) son[fa[i]].pb(i);

    int64 ans = 0;

    dfs(0);

    for(int i = 1 ; i <= N ; ++i) {

	if(dep[i] & 1) ans += C[i].r * C[i].r;

	else ans -= C[i].r * C[i].r;

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}