题解 SP8073 【CIRU

题目链接

Solution 圆的面积并

题目大意：给定(n)个圆,(n leq 1000)求这些圆的面积并

自适应辛普森

---

求圆的面积并我们不好求，但是我们可以(O(nlogn))求出(n)条线段的并，于是我们可以用(f(X))表示直线(x = X)与每个圆的切线的并，然后我们求(int_{-infty}^{infty} f(x);dx)即可

直接上自适应辛普森，不过要注意，如果朴素算法及其容易炸精度(比如圆分布的比较稀疏，你辛普森算法第一层取的(5)个点全都是(0)就gg了，可以分段做辛普森)

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <cstdio>
#include <map>
using namespace std;
const int maxn = 1024;
double eps = 1e-4;
struct Seg{
	double l,r;
	bool operator < (const Seg &rhs)const{return l < rhs.l;}
}seg[maxn];
struct Round{
	double x,y,r;
}val[maxn];
int n;
map<double,double> mp; 
inline double f(double x){
	if(mp[x])return mp[x];
	static Seg seg[maxn];
	int tot = 0;
	for(int i = 1;i <= n;i++){
		double deltay = val[i].r * val[i].r - (val[i].x - x) * (val[i].x - x);
		if(deltay <= eps)continue;
		deltay = sqrt(deltay);
		seg[++tot] = Seg{val[i].y - deltay,val[i].y + deltay};
	}
	sort(seg + 1,seg + 1 + tot);
	double res = 0,last = -1e9;
	for(int i = 1;i <= tot;i++){
		const Seg &now = seg[i];
		if(now.l > last)res += now.r - now.l,last = now.r;
		else if(now.r > last)res += now.r - last,last = now.r;
	}
	return mp[x] = res;
}
inline double simpson(double l,double r){
	double mid = (l + r) / 2.0;
	return (r - l) * (f(l) + f(mid) * 4.0 + f(r)) / 6.0;
}
inline double solve(double l,double r,double now,double eps){
	double mid = (l + r) / 2.0,L = simpson(l,mid),R = simpson(mid,r);
	if(fabs(L + R - now) < eps)return L + R;
	return solve(l,mid,L,eps / 2) + solve(mid,r,R,eps / 2);
}
double l = 1e9,r = -1e9,ans,last = -1e9;
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> val[i].x >> val[i].y >> val[i].r;
		seg[i] = Seg{val[i].x - val[i].r,val[i].x + val[i].r};
		l = min(l,val[i].x - val[i].r);
		r = max(r,val[i].x + val[i].r);
	}
	sort(seg + 1,seg+ 1 + n);
	for(int i = 1;i <= n;i++){
		const Seg &now = seg[i];
		if(now.l > last)ans += solve(now.l,now.r,simpson(now.l,now.r),eps),last = now.r;
		else if(now.r > last)ans += solve(last,now.r,simpson(now.l,now.r),eps),last = now.r;
	}
	cout << setiosflags(ios::fixed) << setprecision(3) << ans << '
';
	return 0;
}