「FJOI2013」圆形游戏

2014年9月23日5,6124

题目描述

在一个无穷大的桌面上有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即执行骗分。。。

 

 

avatar
1 Comment threads
3 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
hzwer Recent comment authors
  Subscribe  
提醒
翁家翌

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