C++(g++ 7.5.0) 解法, 执行用时: 330ms, 内存消耗: 23104K, 提交时间: 2022-11-29 15:28:42

#include<iostream>
#include<cstring>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
const double eps = 1e-8;
struct Op{
    int pos, x, y, r, id, type;
}op[maxn * 2];
int sign[maxn];

int nowx;

inline LL sqr(int x){
    return 1LL * x * x;
}

struct Node{
    int x, y, r, op, id;
    double inter() const{
        if (op) return y + sqrt(sqr(r) - sqr(x - nowx)) + eps;
        return y - sqrt(sqr(r) - sqr(x - nowx));
    }

    bool operator<(const Node &t) const{
        return inter() < t.inter();
    }
};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int x, y, r;
        cin >> x >> y >> r;
        op[++cnt] = {x - r, x, y, r, i, 0};
        op[++cnt] = {x + r, x, y, r, i, 1};
    }
    sort(op + 1, op + cnt + 1, [&](Op &a, Op &b){
        return a.pos < b.pos;
    });
    LL ans = 0;
    set<Node> s;
    for(int i = 1; i <= cnt; i++){
        auto [pos, x, y, r, id, type] = op[i];
        nowx = pos;
        if (type == 0){
            auto it = s.insert({x, y, r, 1, id}).first;
            if (it == s.begin()){
                sign[id] = 1;
            }
            else{
                if (prev(it)->op) sign[id] = sign[prev(it)->id];
                else sign[id] = sign[prev(it)->id] ^ 1;
            }
            s.insert({x, y, r, 0, id});
            if (sign[id]) ans += 1LL * r * r;
            else ans -= 1LL * r * r;
        }
        else{
            s.erase({x, y, r, 1, id});
            s.erase({x, y, r, 0, id});
        }
    }
    cout << ans << '\n';

}

C++ 解法, 执行用时: 531ms, 内存消耗: 28572K, 提交时间: 2022-06-29 16:40:06

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
#define N 200010
using namespace std;
long long T;
struct circle{long long x,y,r;};
struct ppp{long long num,x,o;}b[N<<1];
bool cmp(ppp x,ppp y){return x.x<y.x;}
circle c[N];
long long sqr(long long x){return x*x;}
bool operator <(ppp x,ppp y)
{
	double xx=c[x.num].y+x.o*sqrt(sqr(c[x.num].r)-sqr(T-c[x.num].x));
	double yy=c[y.num].y+y.o*sqrt(sqr(c[y.num].r)-sqr(T-c[y.num].x));
	if(xx!=yy) return xx<yy;
	return x.o<y.o;
}
set<ppp>S;
long long f[N];
int main()
{
	long long n;
	scanf("%lld",&n);
	long long i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].r);
		b[2*i-1]=(ppp){i,c[i].x-c[i].r,1};
		b[2*i]=(ppp){i,c[i].x+c[i].r,-1};
	}
	sort(b+1,b+2*n+1,cmp);
	set<ppp>::iterator it;
	for(i=1;i<=2*n;i++)
	{
		T=b[i].x;
		if(b[i].o==1)
		{
			it=S.upper_bound((ppp){b[i].num,0,-1});
			if(it==S.end()) f[b[i].num]=1;
			else
			{
				if((*it).o==1) f[b[i].num]=-f[(*it).num];
				else f[b[i].num]=f[(*it).num];
			}
			S.insert((ppp){b[i].num,0,-1});
			S.insert((ppp){b[i].num,0,1});
		}
		else
		{
			S.erase((ppp){b[i].num,0,-1});
			S.erase((ppp){b[i].num,0,1});
		}
	}
	long long ans=0;
	for(i=1;i<=n;i++)
	ans+=sqr(c[i].r)*f[i];
	printf("%lld",ans);
}