F题: A Stack of CDs

原题链接:https://ac.nowcoder.com/acm/contest/33190/F

题目大意

现在 $n(1\le n\le 1000)$ 个圆依次放在桌上，每个圆的圆心坐标和半径已知，已知其从下向上的顺序。现在从上向下看，求所有可见圆的可见边的长度和。

题解

对于每一个圆，枚举每个在它上方的圆，记录下被覆盖的部分(用极角保存)，然后对被覆盖的部分取并减去再加上原周长即可。
两个圆的关系分情况讨论:

• 两个圆无重合部分(无影响)
• 下面的圆包含上面的圆(无影响)
• 上面的圆包含下面的圆(下面的圆无贡献)
• 相交

下面只讨论相交的做法

如上图，在 $△ABC$ 中， $AC$ 为圆 $A$ 的半径， $BC$ 为圆 $B$ 的半径， $AB$ 为圆心间的距离，均易求得，因而可由余弦定理求得 $\angle BAD=\angle BAC=\frac{A{B}^2+A{C}^2-B{C}^2}{2AB\cdot AC}$ 。与水平线的夹角 $\angle BAE$ 可由反正切函数求得(传入直线AB的斜率即可)。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

#define sqr(x) ((x)*(x))
const double pi=acos(-1);
const int MAXN=1e3+5;
int n;
double r[MAXN],x[MAXN],y[MAXN];

double dis(int i,int j){//求第i,j个圆心间的距离
	return sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); 
} 

int main()
{
	read(n);
	for(int i=1;i<=n;++i)cin>>x[i]>>y[i]>>r[i];
	double ans=0;
	for(int i=1;i<=n;++i){
		vector<pair<double,double> >v;
		for(int j=i+1;j<=n;++j){
			if(dis(i,j)>=r[i]+r[j])continue;//外离
			if(dis(i,j)<=abs(r[i]-r[j])){//包含上面的圆
				if(r[j]>r[i])v.push_back(make_pair(0,2*pi));//被上面的圆包含,即完全覆盖
				continue;
			}
			double dist=dis(i,j);
			double delta=acos((sqr(r[i])+sqr(dist)-sqr(r[j]))/(2*r[i]*dist));//余弦定理求角
			double base=atan2(y[j]-y[i],x[j]-x[i])+pi;//圆心连线的极角
			double l=base-delta,r=base+delta;//两个边界
			if(l<0){//l<0
				v.push_back(make_pair(0,r));
				v.push_back(make_pair(l+2*pi,2*pi));
			}
			else if(r>2*pi){//l<2*pi
				v.push_back(make_pair(l,2*pi));
				v.push_back(make_pair(0,r-2*pi));
			}
			else v.push_back(make_pair(l,r));//区间完整,直接存入
		}
		ans+=2*pi*r[i];
		if(v.empty())continue; 
		sort(v.begin(),v.end());//pair自动优先按照第一关键字(即l)排序,然后按照第二关键字(即r)进行排序
		double L=v[0].first,R=v[0].second;
		for(int j=1;j<v.size();++j){
			if(R<v[j].first){//当下一段区间与前面的区间断开时,直接结算前面的答案
				ans-=(R-L)*r[i];
				L=v[j].first,R=v[j].second;
			}
			else L=min(L,v[j].first),R=max(R,v[j].second);//直接并下一段区间
		}
		ans-=(R-L)*r[i];//剩余的未结算区间
	}
	cout<<fixed<<setprecision(12)<<ans<<'\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64