题目描述
いつまでも止まらない この胸のときめきで 一緒に踊ろう
随着永不停息的这心中的悸动,一起来跳舞吧!
给定坐标平面上 $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 2 3 4 5 6
| 5 2 1 6 0 4 1 2 -1 3 1 -2 1 4 -1 1
|
样例输出 1
样例解释 1
样例 1 的最优方案与「题目描述」一节中的图形对应。
样例输入 2
1 2 3 4 5 6 7 8 9
| 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
数据范围与提示
$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 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 84
| #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) { 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) { add(j, i); vis[i] = 1; break; } 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.)); }
|