[AC代码] 自适应辛普森求积分

解题思路:
用自适应辛普森求多个圆在矩形ab内的并面积

注意事项:

参考：

www.luogu.com.cn/problem/P4525

www.luogu.com.cn/problem/SP8073

将超出矩形的线段处理为 0-a ，0-b

不处理r=0的圆
参考代码:

#include <bits/stdc++.h>
using namespace std;

#define pdd pair<double,double>
#define l first
#define r second

const int N = 100;
double eps = 1e-6;

int n;
double a,b,x[N],y[N],r[N];

double f(double xi){
	priority_queue<pdd,vector<pdd>,greater<pdd> > pq;
	for(int i = 0;i < n;++i){
		double y1 =r[i]*r[i]-(x[i]-xi)*(x[i]-xi);
		if(y1 < eps)continue;
		y1 = sqrt(y1);
		pq.push(pdd(max(0.0,y[i]-y1),min(b,y[i]+y1)));
	}
	double ret = 0,last = 0;
	while(!pq.empty()){
		pdd seg = pq.top();pq.pop();
		if(seg.l > last)ret += seg.r - seg.l,last = seg.r;
		else if(seg.r > last)ret += seg.r - last,last = seg.r;
	}
	return ret;
}

double simpson(double l,double r){
	double mid = (l+r)/2;
	return (r-l)*(f(l)+4*f(mid)+f(r))/6;
}

double integral(double l,double r,double crt){
	double mid = (l+r)/2.0,L = simpson(l,mid),R = simpson(mid,r);
	if(fabs(crt-L-R)<eps)return L+R;
	return integral(l,mid,L) + integral(mid,r,R);
}

int main(){
	//freopen("in.txt","r",stdin);
	double ctg;
	cin >> a >> b >> ctg >> n;
	ctg = 1.0/tan(ctg/180.0*M_PI);
	for(int i = 0;i < n;++i){
		double z;cin >> x[i] >> y[i] >> z >> r[i];
		x[i] += z * ctg;
	}
	priority_queue<pdd,vector<pdd>,greater<pdd> > pq;
	for(int i = 0;i < n;++i){
		if(r[i]==0)continue;
		pq.push(pdd(max(0.0,x[i]-r[i]),min(a,x[i]+r[i])));
	}
	double last = 0,res = 0;
	while(!pq.empty()){
		pdd seg = pq.top();pq.pop();
		if(seg.l > last)res += integral(seg.l,seg.r,simpson(seg.l,seg.r)),last = seg.r;
		else if(seg.r > last)res += integral(last,seg.r,simpson(last,seg.r)),last = seg.r;
	}
	printf("%.2f\n",a*b-res);
	return 0;
}