[HAOI 2008] 下落的圆盘

题目大意

nn 个圆盘从天而降,后面落下的可以盖住前面的。求最后所有圆的可见弧长和。

1n1,0001 \leqslant n \leqslant 1,000

题目链接

【HAOI 2008】下落的圆盘 - Luogu 2510

题解

对于每个圆,考虑在之后落下的圆,如果覆盖了当前圆,则当前圆无可见弧(废话);如果与后面的圆有交点,用余弦定理计算出弧对应的起止角度(用角度保存弧),最后求出未覆盖的弧的角度,求出弧长加入答案。

代码

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
#include <cstdio>
#include <cmath>
#include <algorithm>
const int MAXN = 1005;
const double PI = acos(-1);
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
double angle() const {
return atan2(y, x);
}
friend double dist(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
};
struct Arc {
double l, r;
Arc(double l = 0, double r = 0) : l(l), r(r) {}
bool operator<(const Arc &another) const {
return l < another.l;
}
};
struct Circle {
double r;
Point o;
Circle() {}
Circle(const Point &o, double r) : o(o), r(r) {}
friend bool contain(const Circle &a, const Circle &b) {
return a.r - b.r >= dist(a.o, b.o);
}
friend Arc getCircleIntersection(const Circle &a, const Circle &b) {
double dis = dist(a.o, b.o);
double th = acos((a.r * a.r - b.r * b.r + dis * dis) / (2 * a.r * dis));
double ath = (b.o - a.o).angle();
return Arc(ath - th, ath + th);
}
} C[MAXN];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf %lf %lf", &C[i].r, &C[i].o.x, &C[i].o.y);
double ans = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
static Arc a[MAXN];
bool flag = false;
for (int j = i + 1; j < n; j++) {
if (contain(C[j], C[i])) {
flag = true;
break;
}
if (!contain(C[i], C[j]) && C[i].r + C[j].r > dist(C[i].o, C[j].o))
a[cnt++] = getCircleIntersection(C[i], C[j]);
}
if (flag) continue;
for (int i = 0; i < cnt; i++) {
if (a[i].l < 0) a[i].l += 2 * PI;
if (a[i].r < 0) a[i].r += 2 * PI;
if (a[i].l > a[i].r) {
a[cnt++] = Arc(0, a[i].r);
a[i].r = 2 * PI;
}
}
std::sort(a, a + cnt);
double temp = 0, curr = 0;
for (int i = 0; i < cnt; i++) {
if (curr < a[i].l) {
temp += a[i].l - curr;
curr = a[i].r;
} else curr = std::max(curr, a[i].r);
}
ans += (temp + 2 * PI - curr) * C[i].r;
}
printf("%.3lf\n", ans);
return 0;
}