「Codeforces Round #418」白金夜话

题目描述#

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

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

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

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

现在需要将这 $n$ 个圆划分为两个集合，每个圆恰好在两个集合中的一个内。

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

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

输入格式#

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

接下来 $n$ 行，每行包含三个整数 $x_i, y_i, r_i$ —— 描述一个圆心位于 ( $x_i, y_i$ )、半径为 $r_i$ 的圆。

输出格式#

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

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

样例#

样例输入 1#

样例输出 1#

1
138.23007676

样例解释 1#

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

样例输入 2#

样例输出 2#

1
289.02652413

数据范围与提示#

$1 \leq n \leq 1000$
$-10^6 \leq x_i,y_i \leq 10^6, 1 \leq r_i \leq 10^6$

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

题解#

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

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

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

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

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

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

就完了。。。

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

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5
using namespace std;
6
inline int read()
7
{
8
    int x=0,f=1;char ch=getchar();
9
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11
    return x*f;
12
}
13
const int MAXN = 1005;
14
#define dis(_, __) (\
15
(((_).x - (__).x) * ((_).x - (__).x)) + \
16
(((_).y - (__).y) * ((_).y - (__).y))\
17
)
18
struct Circle
19
{
20
    double x, y, r;
21
    bool operator < (const Circle &b) const
22
    {
23
        return r < b.r;
24
    }
25
}a[MAXN];
26
struct edge
27
{
28
    int END, next;
29
}v[MAXN << 1];
30
int first[MAXN], p;
31
void add(int a, int b)
32
{
33
    v[p].END = b;
34
    v[p].next = first[a];
35
    first[a] = p++;
36
}
37
bool vis[MAXN];
38
double f[MAXN][2][2], tmp[MAXN][2][2];
39
void DFS(int rt, int fa)
40
{
41
    // vis[rt] = 1;
42
    for (int i = first[rt]; i != -1; i = v[i].next)
43
    {
44
        DFS(v[i].END, rt);
45
        for (int j = 0; j <= 1; j++)
46
            for (int k = 0; k <= 1; k++)
47
                tmp[rt][j][k] += f[v[i].END][j][k];
48
    }
49
    for (int i = 0; i <= 1; i++)
50
        for (int j = 0; j <= 1; j++)
51
        {
52
            f[rt][i][j] = max(
53
                tmp[rt][i ^ 1][j] + a[rt].r * a[rt].r * (i == 0 ? 1 : -1),
54
                tmp[rt][i][j ^ 1] + a[rt].r * a[rt].r * (j == 0 ? 1 : -1)
55
            );
56
        }
57
}
58
int main()
59
{
60
    memset (first, -1, sizeof (first));
61
    int n = read();
62
    for (int i = 1; i <= n; i++)
63
        a[i].x = read(), a[i].y = read(), a[i].r = read();
64
    sort(a + 1, a + n + 1);
65
    for (int i = 1; i <= n; i++)
66
        for (int j = i + 1; j <= n; j++)
67
            if (dis(a[i], a[j]) < a[j].r * a[j].r)
68
            {
69
                // printf ("%d %d\n", j, i);
70
                add(j, i);
71
                vis[i] = 1;
72
                break;
73
            }
74
    // while (1);
75
    double ans = 0;
76
    for (int i = 1; i <= n; i++)
77
        if (!vis[i])
78
        {
79
            DFS(i, 0);
80
            ans += f[i][0][0];
81
        }
82
    printf ("%.15f\n", ans * acos(-1.));
83
    // while (1);
84
}