Codeforces 814D-An overnight dance in discotheque 贪心

119 阅读 0 评论 79 点赞

我是靠谱客的博主现实世界，这篇文章主要介绍Codeforces 814D-An overnight dance in discotheque 贪心，现在分享给大家，希望可以做个参考。

参考http://blog.csdn.net/a664607530/article/details/72921758

题意：就是告诉你有n个圆（跳舞），告诉你圆心和半径，圆两两之间不会有多余一个的交点，所以两圆之间要不是相离要不是内含。有上半场和下半场之分，每个圆只能出现一次，圆不能包含另一个圆，如果一个人跳舞被覆盖奇数次，他的面积就需要被减去，被覆盖偶数次他的面积就会被加上，然后现在问你跳舞合适的最大面积是多少。

解题思路：把所有圈圈被覆盖的次数统计一下，最大那个肯定加，然后奇数大的加进去，偶数大的减掉，最大的可以在上半夜跳，然后奇数大的在下半夜跳

复制代码

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
int n;
double ans;
struct node
{
double x, y, r;
int flag;
}a[1001];
bool cmp(node a, node b)
{
if (a.r == b.r) return a.x == b.x ? a.y < b.y : a.x < b.x;
return a.r > b.r;
}
bool check(node a, node b)
{
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) < (a.r + b.r)*(a.r + b.r);
}
int main()
{
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r), a[i].flag = 0;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (check(a[i], a[j])) a[j].flag++;
for (int i = 1; i <= n; i++)
{
if (!a[i].flag) ans += a[i].r*a[i].r*pi;
else if (a[i].flag % 2) ans += a[i].r*a[i].r*pi;
else ans -= a[i].r*a[i].r*pi;
}
printf("%.8lfn", ans);
}
return 0;
}