C++(clang++ 11.0.1) 解法, 执行用时: 180ms, 内存消耗: 704K, 提交时间: 2023-03-29 08:32:36

#include <iostream>
#include <cmath>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 1e3 + 100;
const double eps = 1e-8, PI = acos(-1);

int n;
double ans[N];
struct Circle
{
    PDD O;
    double r;
    int state;
}c[N];
struct Data
{
    double angle;
    int state;
}data_[2 * N];

int cmp(double a, double b)
{
    if(abs(a - b) < eps)    return 0;
    if(a < b)   return -1;
    return 1;
}

PDD operator - (PDD a, PDD b)
{
    return { a.x - b.x, a.y - b.y };
}

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int get_circle_circle_point(Circle& a, Circle& b, double& angle1, double& angle2)
{
    double d = get_dist(a.O, b.O);
    if(cmp(d, a.r + b.r) > 0 || cmp(d, abs(a.r - b.r)) < 0)     //两圆外离,内含
        return 0;

    PDD v = b.O - a.O;
    double angle = acos((a.r * a.r + d * d - b.r * b.r) / (2 * d * a.r)),
        delta = atan2(v.y, v.x);

    angle1 = delta - angle, angle2 = delta + angle;

    if(angle1 < -PI)
        angle1 += 2 * PI;
    if(angle > PI)
        angle1 -= 2 * PI;
    if(angle2 < -PI)
        angle2 += 2 * PI;
    if(angle2 > PI)
        angle2 -= 2 * PI;

    if(!cmp(d, a.r + b.r) || !cmp(d, abs(a.r - b.r)))
        return 1;
    return 2;
}

double calc(Circle& c, double l, double r)
{
    double res = c.r * c.r * (r - l) + c.O.x * c.r * (sin(r) - sin(l)) -
        c.O.y * c.r * (cos(r) - cos(l));
    return res / 2;
}

bool compare(Data& a, Data& b)
{
    if(cmp(a.angle, b.angle))   return cmp(a.angle, b.angle) < 0;
    return a.state > b.state;
}

void Circle_Union()
{
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i != j && cmp(c[j].r, c[i].r) >= 0
                && cmp(get_dist(c[i].O, c[j].O), c[j].r - c[i].r) <= 0)
                c[i].state ++;

    for(int i = 1; i <= n; i ++)
    {
        int cnt = 0, t = 0;
        double angle1, angle2;
        for(int j = 1; j <= n; j ++)
            if(i != j && get_circle_circle_point(c[i], c[j], angle1, angle2) == 2)
            {
                data_[cnt ++] = { angle1, 1 }, data_[cnt ++] = { angle2, -1 };
                if(cmp(angle1, angle2) > 0)
                    t ++;

            }
        data_[cnt ++] = { -PI, t }, data_[cnt ++] = { PI, -t };
        sort(data_, data_ + cnt, compare);

        int s = c[i].state + data_[0].state;
        for(int j = 1; j < cnt; j ++)
        {
            ans[s] += calc(c[i], data_[j - 1].angle, data_[j].angle);
            s += data_[j].state;
        }
    }
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++)
    {
        scanf("%lf%lf%lf", &c[i].O.x, &c[i].O.y, &c[i].r);
        c[i].state = 1;
    }


    Circle_Union();

    for(int i = 1; i <= n; i ++)
        printf("[%d] = %.3lf\n", i, ans[i] - ans[i + 1]);

    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 188ms, 内存消耗: 2476K, 提交时间: 2022-09-20 20:50:21

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const double PI=acos(-1.0);
double eps=1e-9;
int sgn(double x){
	if(x<-eps)return -1;
	if(x>eps)return 1;
	return 0;
}
struct P{
	double x,y;
	P(){}
	P(double _x,double _y){x=_x,y=_y;}
	P operator+(const P&b)const{return P(x+b.x,y+b.y);}
	P operator-(const P&b)const{return P(x-b.x,y-b.y);}
	P operator*(double b)const{return P(x*b,y*b);}
	P operator/(double b)const{return P(x/b,y/b);}
	double det(const P&b)const{return x*b.y-y*b.x;}
	P rot90()const{return P(-y,x);}
	P unit(){return *this/abs();}
	double abs(){return hypot(x,y);}
};
struct Circle{
	P o;double r;
	bool contain(const Circle&v,const int&c)const{
		return sgn(r-(o-v.o).abs()-v.r)>c;
	}
	bool disjuct(const Circle&v,const int&c)const{
		return sgn((o-v.o).abs()-r-v.r)>c;
	}
};
bool isCC(Circle a,Circle b,P&p1,P&p2){
	if(a.contain(b,0)||b.contain(a,0)||a.disjuct(b,0))return 0;
	double s1=(a.o-b.o).abs();
	double s2=(a.r*a.r-b.r*b.r)/s1;
	double aa=(s1+s2)/2,bb=(s1-s2)/2;
	P mm=(b.o-a.o)*(aa/(aa+bb))+a.o;
	double h=sqrt(max(0.0,a.r*a.r-aa*aa));
	P vv=(b.o-a.o).unit().rot90()*h;
	p1=mm+vv,p2=mm-vv;
	return 1;
}
struct EV{
	P p;double ang;int add;
	EV(){}
	EV(const P&_p,double _ang,int _add){p=_p,ang=_ang,add=_add;}
	bool operator<(const EV&a)const{return ang<a.ang;}
}eve[N*2];
int E,cnt,C,i,j;Circle c[N];
bool g[N][N],overlap[N][N];
double Area[N];
int cX[N],cY[N],cR[N];
bool contain(int i,int j){
	return (sgn(c[i].r-c[j].r)>0||sgn(c[i].r-c[j].r)==0&&i<j)&&c[i].contain(c[j],-1);
}
int main(){
	scanf("%d",&C);
	for(i=0;i<C;i++){
		scanf("%d%d%d",&cX[i],&cY[i],&cR[i]);
		c[i].o=P(cX[i],cY[i]);
		c[i].r=cR[i];
	}
	for(i=0;i<=C;i++)Area[i]=0;
	for(i=0;i<C;i++)for(j=0;j<C;j++)overlap[i][j]=contain(i,j);
	for(i=0;i<C;i++)for(j=0;j<C;j++)g[i][j]=!(overlap[i][j]||overlap[j][i]||c[i].disjuct(c[j],-1));
	for(i=0;i<C;i++){
		E=0;cnt=1;
		for(j=0;j<C;j++)if(j!=i&&overlap[j][i])cnt++;
		for(j=0;j<C;j++)if(i!=j&&g[i][j]){
			P aa,bb;
			isCC(c[i],c[j],aa,bb);
			double A=atan2(aa.y-c[i].o.y,aa.x-c[i].o.x);
			double B=atan2(bb.y-c[i].o.y,bb.x-c[i].o.x);
			eve[E++]=EV(bb,B,1);
			eve[E++]=EV(aa,A,-1);
			if(B>A)cnt++;
		}
		if(E==0)Area[cnt]+=PI*c[i].r*c[i].r;
		else{
			sort(eve,eve+E);
			eve[E]=eve[0];
			for(j=0;j<E;j++){
				cnt+=eve[j].add;
				Area[cnt]+=eve[j].p.det(eve[j+1].p)*0.5;
				double theta=eve[j+1].ang-eve[j].ang;
				if(theta<0)theta+=PI*2;
				Area[cnt]+=theta*c[i].r*c[i].r*0.5-sin(theta)*c[i].r*c[i].r*0.5;
			}
		}
	}
	double ans=0;
	for(i=1;i<=C;i++){
		printf("[%d] = %.3lf\n",i,Area[i]-Area[i+1]);
	}
	return 0;
}