bzoj 1043 下落的圓盤（計算幾何-圓的周長并）

Description

有n個圓盤從天而降，後面落下的可以蓋住前面的。求最後形成的封閉區域的周長。看下面這副圖, 所有的紅色線條的總長度即為所求. 

Input

n ri xi y1 ... rn xn yn

Output

最後的周長，保留三位小數

Sample Input

2

1 0 0

1 1 0

Sample Output

10.472

solution：

對于每一個圓，周遊它之後的圓覆寫它的周長和是多少，計算這段圓弧左右端點的角度，用線段并的方法進行求解

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
int n, top;
double x[1005], y[1005], r[1005];
struct line
{
	double l, r;
	bool operator <(const line &x)const
	{
		return l < x.l;
	}
}q[1005];
double dis(int a, int b)
{
	return sqrt((x[a] - x[b])*(x[a] - x[b]) + (y[a] - y[b])*(y[a] - y[b]));
}
bool cover(int a, int b)
{
	if (r[a] >= r[b] + dis(a, b))return 1;
	return 0;
}
void inter(int a, int b)
{
	double d, st, l;
	d = dis(a, b);
	st = atan2((x[a] - x[b]), (y[a] - y[b]));
	l = acos((r[a] * r[a] + d*d - r[b] * r[b]) / (2.0*r[a] * d));
	q[++top].l = st - l; q[top].r = st + l;
}
double cal(int x)
{
	for (int i = x + 1; i <= n; i++)
		if (cover(i, x))return 0;
	top = 0;
	for (int i = x + 1; i <= n; i++)
		if (!cover(x, i) && r[x] + r[i] >= dis(x, i))inter(x, i);
	double tmp = 0, now = 0;
	for (int i = 1; i <= top; i++)
	{
		if (q[i].l <0)q[i].l += 2 * pi;
		if (q[i].r < 0)q[i].r += 2 * pi;
		if (q[i].l > q[i].r)
		{
			q[++top].l = 0; q[top].r = q[i].r;
			q[i].r = 2 * pi;
		}
	}
	sort(q + 1, q + 1 + top);
	for (int i = 1; i <= top; i++)
		if (q[i].l > now)
		{
		tmp += q[i].l - now;
		now = q[i].r;
		}
		else now = max(now, q[i].r);
		tmp += 2 * pi - now;
		return r[x] * tmp;
}
int main()
{
	scanf("%d", &n);
	double ans = 0;
	for (int i = 1; i <= n; i++)
		scanf("%lf%lf%lf", &r[i], &x[i], &y[i]);
	for (int i = 1; i <= n; i++)
		ans += cal(i);
	printf("%.3lf\n", ans);
	return 0;
}