记录编号	378701	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]下落的圆盘	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2017-03-04 17:50:04	内存使用	4.10 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
typedef pair<db,db> pr;
const int N=1e5+10;
const db pi=acos(-1.0);
int n;db x[N],y[N],r[N];
pr p[N];
db sqr(db x){return x*x;}
int main()
{
	freopen("disc.in","r",stdin);
	freopen("disc.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
	db ans=0;
	for (int i=1;i<=n;i++){
		int cnt=0;db now=0;
		for (int j=i+1;j<=n;j++){
			db d=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
			if (d>r[i]+r[j]) continue;
			if (d<r[j]-r[i]) goto end;
			db alpha=atan2(y[j]-y[i],x[j]-x[i])+pi;
			//余弦定理 
			db k=(sqr(r[i])+sqr(d)-sqr(r[j]))/(2*r[i]*d);
			if (k>1) k=1;
			if (k<-1) k=-1;
			db phi=acos(k);
			if (alpha<phi){
				p[++cnt]=pr(0,alpha+phi);
				p[++cnt]=pr(alpha-phi+2*pi,2*pi);
			}
			else if (alpha+phi>2*pi){
				p[++cnt]=pr(0,alpha+phi-2*pi);
				p[++cnt]=pr(alpha-phi,2*pi);
			}
			else p[++cnt]=pr(alpha-phi,alpha+phi);
		}
		sort(p+1,p+cnt+1);
		for (int j=1;j<=cnt;j++){
			if (now<p[j].first) ans+=r[i]*(p[j].first-now);
			now=max(now,p[j].second);
		}
		ans+=r[i]*(2*pi-now);
		end:;
	}
	printf("%.3lf\n",ans);
	return 0;
}