1124 字
6 分钟
「Codeforces Round #418」白金夜话
2018-04-12

题目描述#

いつまでも止まらない この胸のときめきで 一緒に踊ろう
随着永不停息的这心中的悸动,一起来跳舞吧!

给定坐标平面上 nn 个圆。任意两个圆的边界至多只有一个公共点 —— 即它们必定相离或相切。

对于一个圆的集合,定义其异或面积为平面上被该集合中奇数个圆覆盖的图形面积。

Figure 1
对于这个集合,浅蓝色部分图形的面积被计入异或面积内。

现在需要将这 nn 个圆划分为两个集合,每个圆恰好在两个集合中的一个内。
Figure 2

对于这个集合,浅蓝色部分图形的面积被计入异或面积内。

请求出合法的划分方案中,两个集合分别计算的异或面积之和的最大值。

输入格式#

输入的第一行包含一个正整数 nn —— 圆的数目。

接下来 nn 行,每行包含三个整数 xi,yi,rix_i, y_i, r_i —— 描述一个圆心位于 (xi,yix_i, y_i)、半径为 rir_i 的圆。

输出格式#

输出一个十进制实数 —— 合法的划分方案中,两个集合异或面积之和的最大值。

当选手答案与参考答案的相对误差或绝对误差不超过 10910^{-9} 时被视为正确。形式化地,若选手输出为 aa,参考答案为 bb,答案被视为正确当且仅当 abmax(1,b)109\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}

样例#

样例输入 1#
5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1
样例输出 1#
138.23007676
样例解释 1#

样例 1 的最优方案与「题目描述」一节中的图形对应。

样例输入 2#
8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
样例输出 2#
289.02652413

数据范围与提示#

1n10001 \leq n \leq 1000
106xi,yi106,1ri106-10^6 \leq x_i,y_i \leq 10^6, 1 \leq r_i \leq 10^6

ささやかだけど かけがえのない 歴史を重ねて
渺小平凡却无可替代的事物一点点重现着历史
偽りさえも 本当になる 君の隣りで
即使谎言在你身旁也会变得如此真实
                  ——「白金ディスコ」

题解#

其实不难吧, 但思路还是不错的。

首先在平面的几何关系不是很好搞, 我们发现题目中保证必定相离或相切

那么圆就只有包含或者相离的关系

可以抽象成一颗树(森林)。
在图中包含他的圆为他的祖先
那么我们一个圆的贡献就与他在树上的深度有关

我们现在要把这个森林分成不相交的两部分

考虑 DPDP
定义 F[i][j][k]F[i][j][k] 表示以 ii 为根的子树一个集合的深度的奇偶为 jj 另一个为集合的深度的奇偶为 kk 的最大面积和 转移的时候先将子树合并
在枚举这个点放在哪个集合里

就完了。。。

好像还有一个贪心的做法。
但我不会啊。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN = 1005;
#define dis(_, __) (\
(((_).x - (__).x) * ((_).x - (__).x)) + \
(((_).y - (__).y) * ((_).y - (__).y))\
)
struct Circle
{
double x, y, r;
bool operator < (const Circle &b) const
{
return r < b.r;
}
}a[MAXN];
struct edge
{
int END, next;
}v[MAXN << 1];
int first[MAXN], p;
void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
bool vis[MAXN];
double f[MAXN][2][2], tmp[MAXN][2][2];
void DFS(int rt, int fa)
{
// vis[rt] = 1;
for (int i = first[rt]; i != -1; i = v[i].next)
{
DFS(v[i].END, rt);
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 1; k++)
tmp[rt][j][k] += f[v[i].END][j][k];
}
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
{
f[rt][i][j] = max(
tmp[rt][i ^ 1][j] + a[rt].r * a[rt].r * (i == 0 ? 1 : -1),
tmp[rt][i][j ^ 1] + a[rt].r * a[rt].r * (j == 0 ? 1 : -1)
);
}
}
int main()
{
memset (first, -1, sizeof (first));
int n = read();
for (int i = 1; i <= n; i++)
a[i].x = read(), a[i].y = read(), a[i].r = read();
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (dis(a[i], a[j]) < a[j].r * a[j].r)
{
// printf ("%d %d\n", j, i);
add(j, i);
vis[i] = 1;
break;
}
// while (1);
double ans = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
{
DFS(i, 0);
ans += f[i][0][0];
}
printf ("%.15f\n", ans * acos(-1.));
// while (1);
}
「Codeforces Round #418」白金夜话
https://www.nekomio.com/posts/145/
作者
NekoMio
发布于
2018-04-12
许可协议
CC BY-NC-SA 4.0