[BZOJ 1043] [HAOI2008]下落的圆盘

题目链接

BZOJ 1043

做法

博主的计算几何是在是太差了,只能做做这种入门题。
我们发现$n$的范围并不大,我们可以考虑对于每个圆,算出后面每个圆覆盖他的部分。
覆盖他的部分我们把弧对应到圆心角的一个区间。
加入我们现在要算圆$i$被圆$j$覆盖的圆心角的区间。
首先先特判圆$i$和圆$j$相离,以及圆$j$被圆$i$包含的情况。
如果圆$i$被圆$j$包含,那么$i$圆心角整个区间被覆盖。
我们画个图可以发现,$i$的圆心,两圆的一个交点,$j$的圆心,构成一个三角形。
用余弦定理可以算出角度,再计算两个圆心的极角,就可以把弧对应到圆心角的一段区间上了。
现在问题就变成了有一条线段,在上面覆盖一些线段,求没有被覆盖的长度。按左端点排序后扫一遍就好了。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (1005)
using namespace std;
int n,t;
double pi=acos(-1),res,ans,maxen;
double x[N],y[N],r[N];
struct line{
double st,en;
}kill[N<<1];
inline bool cmp(line a,line b){
return a.st<b.st;
}
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
inline double sqr(double x){
return x*x;
}
int main(){
read(n);
for (int i=1;i<=n;i++){
scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
}
for (int i=1;i<=n;i++){
t=0;
for (int j=i+1;j<=n;j++){
double dis=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
if (dis>=r[i]+r[j]) continue;// 相离
if (r[i]>r[j]&&dis+r[j]<=r[i]) continue;//a 包含 b
if (r[i]<r[j]&&dis+r[i]<=r[j]){//b 包含 a
kill[++t]=(line){0,2*pi};
break;
}
double alpha=(sqr(r[i])+sqr(dis)-sqr(r[j]))/(2*dis*r[i]);
double beta=atan2(y[j]-y[i],x[j]-x[i]);
alpha=acos(alpha);
//printf("emm %.3lf %.3lf\n",alpha,beta);
double l=beta-alpha,r=beta+alpha;
if (l<0) l+=2*pi;
if (r<0) r+=2*pi;
if (l>r) kill[++t]=(line){0,r},kill[++t]=(line){l,2*pi};
else kill[++t]=(line){l,r};
}
sort(kill+1,kill+t+1,cmp);
//for (int j=1;j<=t;j++) printf("kill %.3lf %.3lf\n",kill[j].st,kill[j].en);
if (t==0){
ans+=r[i]*2*pi;
continue;
}
kill[++t].st=2*pi;
maxen=0;
res=kill[1].st;
for (int j=1;j<t;j++){
maxen=max(maxen,kill[j].en);
if (maxen<kill[j+1].st) res+=kill[j+1].st-maxen;
}
ans+=res*r[i];
}
printf("%.3lf",ans);
return 0;
}