转载一个板子

自适应辛普森法乱搞

https://blog.csdn.net/qq_45735851/article/details/115309408

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1007;
const double eps=1e-8;
typedef pair<double,double>PDD;

struct Circle{
	PDD o;
	double r;
}c[N];

int n;
PDD q[N];

int judge(double a,double b){
	if(fabs(a-b)<eps) return 0;//相等
	if(a<b) return -1;
	return 1; 
}

double f(double x){
	int cnt=0;
	for(int i=0;i<n;i++){
		double X=fabs(c[i].o.x-x),R=c[i].r;
		if(judge(X,R)<0){
			double Y=sqrt(R*R-X*X);
			q[cnt++]={c[i].o.y-Y,c[i].o.y+Y}; 
		}
	}
	if(!cnt) return 0;
	sort(q,q+cnt);
	double st=q[0].x,ed=q[0].y,res=0; //区间合并
	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 mid=(l+r)/2;
	return (r-l)*(f(l)+4*f(mid)+f(r))/6; 
}

double asr(double l,double r,double s){ //递归自适应 
	double mid=(l+r)/2;
	double lf=simpson(l,mid),rg=simpson(mid,r);
	if(fabs(s-lf-rg)<eps) return lf+rg;
	return asr(l,mid,lf)+asr(mid,r,rg);
}

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++) cin>>c[i].o.x>>c[i].o.y>>c[i].r;
	double l=-2000,r=2000;
	printf("%.3lf\n",asr(l,r,simpson(l,r)));
	return 0;
}