YZOJ P2050 [FJOI2013]圆形游戏

时间限制：8000MS      内存限制：262144KB

难度：\(8.0\)

• 题目描述

在一个无穷大的桌面上有 \(n\) 个圆形，保证任意两个圆相离或者相含，不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏，以 Alice 为先手，双方以如下步骤轮流游戏：

1，选定一个圆 \(A\)，把 \(A\) 以及所有完全在 \(A\) 内部的圆都删除；

2，如果在自己回合无法找到可删除的圆，则输掉比赛。

假设 Alice 和 Bob 都非常聪明，请问最终谁能够取得胜利？请编程输出最终获胜的人。

• 输入格式

输入数据的第一行为一个正整数 \(T\)，表示数据组数。

接下来 \(T\) 组数据，对于每组数据，第一行包含 \(1\) 个正整数 \(n\)，表示圆形的个数。

之后 \(n\) 行，每行为 \(3\) 个整数 \(x\)、\(y\) 和 \(r\) ，分别表示圆形的圆心坐标以及圆的半径。

• 输出格式

假设 Alice 最后获胜，则输出一行 “Alice”（不包括引号），否则输出 “Bob” 。

• 样例输入

• 样例输出

• 数据规模与约定

\(100\%\) 的数据满足 \(T \leq 100\)，\(n \leq m20000\)，\(\left|x\right|, \left|y\right|, r \leq 10^8\) 。

 

 

 

---

 

 

 

三·原题套在一起wwwww

首先把 \(n\) 个圆按照半径从小到大排序，那么对于第 \(i\) 个圆，在半径比它大的圆中找到第一个包含它的圆 \(j\) ，\(i \rightarrow\) 连边，那么此时会连成一个森林。

若再添加一个 \(x=0, y=0, r=\infty\) 的 \(0\) 号圆，那么此时会连成一棵以 \(0\) 为根节点的树。

然后就是一个 SG函数 啦，在上面 DP 一下，有 \(f_o = (f_{s_1}+1) \oplus (f_{s_2}+1) \oplus \cdots\) ，若 \(o\) 为叶子结点则 \(f_o=0\) 。（其实我也不知道为什么

这样转移是 \(O(n)\) 的，但是建树却是 \(O(n^2)\) 的，想办法优化。

其实可以使用扫描线维护这些圆的位置关系。

把圆拆成两个事件，\(x-r\) 插入且 \(x+r\) 弹出，并且把这个圆拆成上半圆和下半圆，近似看成右括号和左括号，那么其实就是要动态维护一个括号序列。

并且在 插入/弹出 前圆的位置关系都是不会发生改变的。

这样，例如 (())就是包含关系，()()就是相离关系。

要找出当前圆被哪一个圆完全包含，就是找当前左括号的前驱：若为左括号则被其包含，若为右括号则它们同时被另一个圆包含。

发现可以使用平衡树维护括号序列，时间复杂度 \(O(n \log n)\) 。