记录编号	214805	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]下落的圆盘	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2015-12-18 11:05:48	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef double LL;
#define sqr(x) ((x)*(x))
const int SIZEN=5010;
const double PI=acos(-1.0);
int N;
LL X[SIZEN],Y[SIZEN],R[SIZEN];
void add_interval(vector<pair<double,int> > &a,double l,double r){
	//规定极角从-PI到PI 
	if(r>PI){
		a.push_back(make_pair(l,1));
		a.push_back(make_pair(PI,-1));
		a.push_back(make_pair(-PI,1));
		a.push_back(make_pair(r-2*PI,-1));
	}
	else if(l<=-PI){
		a.push_back(make_pair(l+2*PI,1));
		a.push_back(make_pair(PI,-1));
		a.push_back(make_pair(-PI,1));
		a.push_back(make_pair(r,-1));
	}
	else{
		a.push_back(make_pair(l,1));
		a.push_back(make_pair(r,-1));
	}
}
double calc(int i){//计算i号圆的贡献长度 
	vector<pair<double,int> > cov;
	for(int j=i+1;j<=N;j++){
		LL dis=sqr(X[i]-X[j])+sqr(Y[i]-Y[j]);
		if(sqr(R[i]-R[j])>=dis&&R[j]>=R[i]) return 0;//被j完全盖住
		if(sqr(R[i]+R[j])<=dis||sqr(R[i]-R[j])>=dis) continue;//相离,或i盖住了j,则不予理会j 
		double c=atan2(Y[j]-Y[i],X[j]-X[i]);
		//用余弦定理,过两圆心及两圆的交点作三角形 
		double a=acos((sqr(R[i])+dis-sqr(R[j]))/(2*R[i]*sqrt(1.0*dis)));
		add_interval(cov,c-a,c+a);
	}
	double ans=2*PI;
	sort(cov.begin(),cov.end());
	int cnt=0;double nowl;
	for(int i=0;i<cov.size();i++){
		if(cov[i].second==1){
			if(!cnt) nowl=cov[i].first;
			cnt++;
		}
		else if(cov[i].second==-1){
			cnt--;
			if(!cnt) ans-=cov[i].first-nowl;
		}
	}
	return ans*R[i];
}
void work(void){
	double ans=0;
	for(int i=1;i<=N;i++) ans+=calc(i);
	printf("%.03lf\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%lf%lf%lf",&R[i],&X[i],&Y[i]);
	}
}
int main(void){
	freopen("disc.in","r",stdin);
	freopen("disc.out","w",stdout);
	read();
	work();
	return 0;
}