Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 593 Accepted Submission(s): 164
Problem Description
There are n circles on a infinitely large table.With every two circle, either one contains another or isolates from the other.They are never crossed nor tangent.
Alice and Bob are playing a game concerning these circles.They take turn to play,Alice goes first:
1、Pick out a certain circle A,then delete A and every circle that is inside of A.
2、Failling to find a deletable circle within one round will lost the game.
Now,Alice and Bob are both smart guys,who will win the game,output the winner's name.
Alice and Bob are playing a game concerning these circles.They take turn to play,Alice goes first:
1、Pick out a certain circle A,then delete A and every circle that is inside of A.
2、Failling to find a deletable circle within one round will lost the game.
Now,Alice and Bob are both smart guys,who will win the game,output the winner's name.
Input
The first line include a positive integer T<=20,indicating the total group number of the statistic.
As for the following T groups of statistic,the first line of every group must include a positive integer n to define the number of the circles.
And the following lines,each line consists of 3 integers x,y and r,stating the coordinate of the circle center and radius of the circle respectively.
n≤20000，|x|≤20000，|y|≤20000，r≤20000。
As for the following T groups of statistic,the first line of every group must include a positive integer n to define the number of the circles.
And the following lines,each line consists of 3 integers x,y and r,stating the coordinate of the circle center and radius of the circle respectively.
n≤20000，|x|≤20000，|y|≤20000，r≤20000。
Output
If Alice won,output “Alice”,else output “Bob”
Sample Input
2
1
0 0 1
6
-100 0 90
-50 0 1
-20 0 1
100 0 90
47 0 1
23 0 1
Sample Output
Alice
Bob
Author
FZUACM
Source
给出很多个园，要么相交，要么相离。如果删掉一个圆，则会删掉其中所有的。可以转化成树的删边
（咳咳！表示并不会这个方法，学习下 而且HDU上C++会超时）
树的删边游戏
规则如下:
给出一个有 N 个点的树,有一个点作为树的根节点。
游戏者轮流从树中删去边,删去一条边后,不与根节点相连的
部分将被移走。
谁无路可走谁输。
我们有如下定理:
[定理]
叶子节点的 SG 值为 0;
中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef unsigned long long ll;
const int N = 20003;
struct P
{
int x, y, r;
} p[N];
bool cmp(P a, P b)
{
return a.r < b.r;
}
int n;
struct Edge
{
int v, next;
} e[N] ;
int head[N], m;
void add(int from ,int to)
{
e[m].v = to;
e[m].next = head[from];
head[from] = m++;
}
int dfs(int u)
{
int temp = 0;
for(int i = head[u];~i;i = e[i].next)
temp ^= dfs(e[i].v) + 1;
return temp;
}
int main()
{
int re;
cin>>re;
while ( re-- )
{
memset(head, -1, sizeof head);
m= 0;
scanf("%d", &n);
for (int i=0; i<n; i++)
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].r);
sort(p ,p+n, cmp);
int rt = n;
for (int i=0; i<n; i++)
{
int flag = 0;
for (int j=i+1; j<n; j++) // r[j] > r[i]
{
ll a = ll((p[i].x-p[j].x)*(p[i].x-p[j].x))+ll((p[i].y-p[j].y)*(p[i].y-p[j].y));
ll b = ll(p[j].r - p[i].r)*ll(p[j].r - p[i].r);
if (a < b)
{
flag = 1;
add(j, i);
break;
}
}
if (!flag)
{
add(rt, i); //如果找不到一个圆可以包含，则用n包含，即虚拟最大的圆，可充当根节点
}
}
int ans = dfs(rt);
puts(ans ? "Alice" : "Bob");
}
return 0;
}