【FJOI2013】圆形游戏

2014年9月23日2,4474

题目描述

在一个无穷大的桌面上有n个圆形,保证任意2个圆相离或者相含,不存在相切或相交。现在Alice和Bob在玩一个圆形游戏,以Alice为先手,双方以如下步骤轮流游戏:
1)  选定一个圆A,把A以及所有完全在A内部的圆都删除;
2)  如果在自己回合无法找到可删除的圆,则输掉比赛。
假设Alice和Bob都非常聪明,请问最终谁能够取得胜利?请编程输出最终获胜的人。

输入

输入数据的第一行为一个正整数T,表示数据组数。接下来T组数据,对于每组数据,第一行包含1个正整数n,表示圆形的个数。之后n行,每行为3个整数x、y和r,分别表示圆形的圆心坐标以及圆的半径。
输入数据保证:40%的数据满足n≤1000;100%的数据满足T≤100,n≤20000,|x|≤20000,|y|≤20000,r≤20000。

输出

假设Alice最后获胜,则输出一行“Alice”(不包括引号),否则输出“Bob”。

样例输入

样例输出

题解

扫描线处理圆的包含关系。。

然后树上删边游戏。。。

但是我发现。。这题每个圆要获得包含它的最小的圆。。。

我只会获得包含它的最大的圆。。

于是我进行了骗分。。在最大的圆的子树中找包含它最小的。。。

于是最后一个点T了

然后我机智的特判了个n<=10000即执行骗分。。。

 

 

  • 翁家翌2015年3月18日 下午5:12 回复

    你们OJ上的数据是哪个学长做的
    数据有错
    圆有交。。。比如第9个点有这两行
    -42656 -37409 25922
    -42909 -32626 29436

    #1  
    • hzwer2015年3月18日 下午6:21 回复
      admin

      不知道啊

      #11
      • 翁家翌2015年3月18日 下午7:03 回复

        6,7,9,10号点,你问一下

        #12
        • hzwer2015年3月18日 下午7:18 回复
          admin

          这好早以前的事情了我问谁去。。

          #13