bzoj1043: [HAOI2008]下落的圆盘

用余弦定理求出覆盖的极角区域，然后就是简单的线段覆盖

const int N = 1010;
struct Circle {
	DB Ox, Oy, R;
	Circle() {}
	Circle(DB _Ox, DB _Oy, DB _R) : Ox(_Ox), Oy(_Oy), R(_R) {}
	inline DB Dis(Circle &B) {
		return sqrt(sqr(Ox - B.Ox) + sqr(Oy - B.Oy));
	}
} Dat[N];
int n;

inline void Input() {
	scanf("%d", &n);
	Rep(i, n) scanf("%lf%lf%lf", &Dat[i].R, &Dat[i].Ox, &Dat[i].Oy);
}

typedef pair<DB, DB> DD;
vector<DD> Count;
const DB Eps = 1e-6, Dpi = pi * 2.0;
inline int See(Circle &A, Circle &B) {
	// 0 -> xiangqie or xiangli
	// 1 -> baohan 2 -> beibaohan
	// 3 -> xiangjiao
	DB Dis = A.Dis(B);
	if(Dis > A.R + B.R || fabs(Dis - A.R + B.R) < Eps) return 0;
	if(Dis + B.R < A.R || fabs(Dis + B.R - A.R) < Eps) return 1;
	if(Dis + A.R < B.R || fabs(Dis + A.R - B.R) < Eps) return 2;
	return 3;
}
inline DB Solve(int Now) {
	Count.clear();
	For(i, Now + 1, n - 1) {
		Circle &A = Dat[Now], &B = Dat[i];
		int Type = See(A, B);
		if(Type < 2) continue;
		if(Type == 2) return 0;
		
		DB Dis = A.Dis(B), Sita, Alpha;
		Sita = atan2(B.Oy - A.Oy, B.Ox - A.Ox);
		Alpha = acos((sqr(Dis) + sqr(A.R) - sqr(B.R)) / (2.0 * Dis * A.R));
		DB Left = Sita - Alpha, Right = Sita + Alpha;
		if(Right < 0) Left += Dpi, Right += Dpi;
		else if(Left < 0) Count.pub(DD(Left + Dpi, Dpi)), Left = 0;
		if(Right > Dpi) Count.pub(DD(0, Right - Dpi)), Right = Dpi;
		if(Left < Right && Right - Left > Eps) Count.pub(DD(Left, Right));
	}
	
	DB Ret = Dpi;
	DD Size = DD(0, 0);
	sort(Count.begin(), Count.end());
	FU(it, Count) {
		if(Size.sd < it->ft) {
			Ret -= Size.sd - Size.ft;
			Size = *it;
		} else Size.sd = max(Size.sd, it->sd);
	}
	Ret -= Size.sd - Size.ft;
	return max(Ret, 0.0) * Dat[Now].R;
}

inline void Solve() {
	DB Ans = 0;
	Rep(i, n) Ans += Solve(i);
	printf("%.3lf\n", Ans + Eps);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1043");
	#endif
	Input();
	Solve();
	return 0;
}