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

Posted on | In , | Views:

题目链接

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;
}