自适应辛普森积分求圆的面积并
cpp
const double eps=1e-12;
int n;
struct Point{
double x,y;
bool operator<(const Point &t)const{
return x!=t.x?x<t.x:y<t.y;
}
};
struct Circle{
Point p;
double R;
} c[N];
Point q[N];
int dcmp(double x,double y){
if(fabs(x-y)<eps)return 0;
if(x<y)return -1;
return 1;
}
double f(double x){
int cnt=0;
for(int i=0;i<n;i++){
double X=fabs(x-c[i].p.x),R=c[i].R;
if(dcmp(X,R)<0){
double Y=sqrt(R*R-X*X);
q[cnt++]={c[i].p.y-Y,c[i].p.y+Y};
}
}
if(!cnt)return 0;
sort(q,q+cnt);
double res=0,st=q[0].x,ed=q[0].y;
for(int i=1;i<cnt;i++){
if(q[i].x<=ed)ed=max(ed,q[i].y);
else{
res+=ed-st;
st=q[i].x,ed=q[i].y;
}
}
return res+ed-st;
}
double simpson(double l,double r,double sl,double sr){
double mid=(l+r)/2;
return (r-l)*(sl+4*f(mid)+sr)/6;
}
double asr(double l,double r,double s,double sl,double sr){
double mid=(l+r)/2;
double S=f(mid);
double left=simpson(l,mid,sl,S),right=simpson(mid,r,S,sr);
if(fabs(left+right-s)<eps)return left+right;
return asr(l,mid,left,sl,S)+asr(mid,r,right,S,sr);
}
double dis(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(){ //预处理，删除被包含的圆
int cnt = 0;
for (int i = 0, j; i < n; ++i) {
for (j = i+1; j < n; ++j) {
if(c[i].R-c[j].R + dis(c[i].p, c[j].p) < eps){
break;
}
}
if(j >= n) c[cnt++] = c[i];
}
n = cnt;
}
vector<Point> segs;
void merge(){
sort(segs.begin(),segs.end());
vector<Point> res;
double st=segs[0].x,ed=segs[0].y;
for(int i=1;i<segs.size();i++){
if(dcmp(segs[i].x,ed)<=0)ed=max(ed,segs[i].y);
else{
res.push_back({st,ed});
st=segs[i].x,ed=segs[i].y;
}
}
res.push_back({st,ed});
segs.swap(res);
}
void solve(){
cin>>n;
for(int i=0;i<n;i++)cin>>c[i].p.x>>c[i].p.y>>c[i].R,segs.push_back({c[i].p.x - c[i].R, c[i].p.x + c[i].R});
sort(c,c+n,[&](Circle a,Circle b){
return a.R<b.R;
});
init();
merge();
double res=0;
for(int i=0;i<segs.size();i++){
auto [l,r]=segs[i];
res+=asr(l,r,f((l+r)/2),f(l),f(r));
}
cout<<setprecision(3)<<fixed<<res<<"\n";
}