「BZOJ1043」[HAOI2008]下落的圆盘

Description

nn个圆盘从天而降,后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.

Input

第一行为11个整数。
接下来nn行每行33个实数,ri,xi,yir_i,x_i,y_i,表示下落时第ii个圆盘的半径和圆心坐标.

Output

最后的周长,保留三位小数

Sample Input

1
2
3
2
1 0 0
1 1 0

Sample Output

1
10.472

HINT

n1000n\leq 1000

Solution

明确一点,xx轴正方向为角度起始点,逆时针依次[0,360][0^\circ,360^\circ]
盗用一张图:

通过余弦定理可以求出

cosCAB=AC2+AB2BC22ACAB\cos\angle {CAB}=\frac{AC^2+AB^2-BC^2}{2AC\cdot AB}

然后反余弦,可以得到CAD\angle {CAD}的弧度制下的大小。
接下来就是核心:
对于一个圆ii,枚举圆j[i+1,n]j\in[i+1,n],把所有能覆盖i圆i的弧都加到bb数组里,然后跑线段覆盖就行了。
计算角度有一个前提,就是两个圆必须有交点,然而当两个圆内含或者相离的时候就要跳过了,如果圆ii被圆jj包含,那么就要跳过圆ii的答案。

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
78
79
80
81
82
83
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2110*4;
int n;
struct Cir {
double x, y, r;
}a[N];
double dst(double x1, double y1, double x2, double y2) {
return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
bool get(Cir x, Cir y) {
double t = dst(x.x, x.y, y.x, y.y);
return t < (x.r + y.r) && !(t < x.r - y.r); //相离或者y内含于x
}
struct T {
double l, r;
}b[N];
bool cmp(T _x, T _y) {
return _x.l < _y.l;
}
const double pi = acos(-1);
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf",&a[i].r, &a[i].x,&a[i].y);
}
double ans = 0;
for(int i = 1; i <= n; ++i) {
int tot = 0;
bool fg = 0;
for(int j = i + 1; j <= n; ++j) if(get(a[i], a[j])){
double d = dst(a[i].x, a[i].y, a[j].x, a[j].y);
if(d < a[j].r - a[i].r) { //i内含于j
fg = 1;
break;
}
double r1 = a[i].r;
double r2 = a[j].r;
double t = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d);
t = acos(t);
double mid = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
b[++tot].l = mid - t;
b[tot].r = mid + t;
if(b[tot].l < 0 && b[tot].r < 0) {
b[tot].l += pi * 2;
b[tot].r += pi * 2;
} else if(b[tot].l < 0 && b[tot].r > 0) {
b[tot].l = 0;
b[tot].r = mid + t;
b[++tot].l = mid - t + pi * 2;
b[tot].r = pi * 2;
}
}
if(fg) continue;
b[++tot] = (T){0,0};
b[++tot] = (T){pi * 2, pi * 2};
sort(b + 1, b + 1 + tot, cmp);
double last=0;
for(int j = 1; j <= tot; ++j) {
ans += max(0.0, (b[j].l - last) * a[i].r);
last = max(last, b[j].r);
}
}
printf("%.3lf\n",ans);
return 0;
}