SP8073 CIRU - 圆并集的面积

前言

初中生第一次接触 Simpson 公式，有写得不好的请指出。

本题要求圆并集的面积，而 P1222 三角形是求三角形并集的面积，也可以用本题的方法计算。

前置

积分、Simpson 公式、自适应 Simpson。
勾股定理、圆等基础内容。

正文

（1）Simpson 公式

将原函数拟合成二次函数，得：

\int_a^bf(x)dx\approx\frac{ (b-a)[f(a)+4f(\frac{a+b}{2})+f(b)] }{6}

（2）自适应 Simpson

由于直接计算的误差较大，因此可以分段计算，直到满足精度需求。

（3）主体思路

可以发现并集的面积是所有

x=d

的直线上被圆覆盖长度的积，也就是

f(x)

的值。

将

x

连续的一段并集统一求答案，加和即为面积。

注意大套小的情况，去重可以减少时间复杂度~不去重过不了~。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-3;
int n;
double x[1005] , y[1005] , r[1005];
bool vis[5005] , in[1005];
map <double , int> c;
vector <int> S;
double f (double X)
{
	c.clear ();
	for (int i : S) if (x[i] - r[i] <= X && X <= x[i] + r[i])
	{
		double l = sqrt (r[i] * r[i] - (X - x[i]) * (X - x[i])) , r;
		r = l + y[i];
		l = y[i] - l;
		c[l] ++ , c[r] --;
	}
	double ans = 0 , lst = 0;
	int cnt = 0;
	for (auto it : c)
	{
		if (cnt)
			ans += it.first - lst;
		lst = it.first , cnt += it.second;
	}
	return ans;
}
double simpson (double l , double r)
{
	return (f (l) + 4 * f ((l + r) / 2) + f (r)) * (r - l) / 6;
}
double solve (double l , double r , double ans , double eps)
{
	double mid , ls , rs;
	mid = (l + r) / 2;
	ls = simpson (l , mid) , rs = simpson (mid , r);
	if (fabs (ls + rs - ans) <= max (eps , 1e-9)) return ls + rs;
	return solve (l , mid , ls , eps / 2) + solve (mid , r , rs , eps / 2);
}
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	cin >> n;
	for (int i = 1;i <= n;i ++)
	{
		cin >> x[i] >> y[i] >> r[i];
		x[i] += 2500;
		for (int j = x[i] - r[i];j <= x[i] + r[i];j ++)
			vis[j] = 1;
	}
	for (int i = 1;i <= n;i ++) for (int j = 1;j <= n && !in[i];j ++) if (i != j && !in[j])
	{
		double dis = sqrt ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
		in[i] = r[j] - dis - r[i] >= -EPS;
	}
	for (int i = 1;i <= n;i ++)
		if (!in[i])
			S.push_back (i);
	int l = 0 , r = 0;
	double ans = 0;
	for (int i = 0;i <= 5000;i ++)
	{
		if (!vis[i])
		{
			if (r)
				ans += solve (l , r , simpson (l , r) , EPS) , r = 0;
			l = i;
			continue;
		}
		if (!r) r = i;
		else ++ r;
	}
	printf ("%.3f" , ans);
	return 0;
}

题解：SP8073 CIRU - The area of the union of circles

文章操作