hdu5299 Circles Game

Circles Game

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1427Accepted Submission(s): 451

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.

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。

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 2015 Multi-University Training Contest 1

顯然圓的包含關系可以構成一片森林，然後問題就可以轉化為：每一步可以刪除森林的一棵樹或者某樹的一棵子樹，不能刪者輸。這樣，問題就變成經典的樹上刪邊游戲了。

樹上刪邊游戲有一個很重要的結論：葉子節點的SG值為0，中間節點的SG值為它的所有子節點的SG值加1後的異或和。(證明詳見賈志豪論文《組合游戲略述——淺談SG游戲的若干拓展及變形》)

現在，我們的主要問題就是如何把圓的包含關系轉化為森林。這裡要用到圓的掃描線算法。首先對於每個圓，創建兩個時間點，一個進入一個離開，再對所有時間點從小到大排序。然後逐個處理時間點，用set維護所有圓，每遇到一個進入時間，分情況討論圓的位置關系，然後把這個圓插入set中。每遇到一個離開時間，從set中刪除這個圓。

 

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 20010
using namespace std;
int t,n,cnt,tt,tmp;
int head[maxn],fa[maxn];
struct cir{int x,y,r;}a[maxn];
struct edge_type{int next,to;}e[maxn*2];
struct bor
{
	int x,f,id;
	friend bool operator < (bor a,bor b)
	{
		if (a.x==b.x) return a.f s;
set::iterator it;
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;
}
inline void add_edge(int x,int y)
{
	e[++cnt]=(edge_type){head[x],y};
	head[x]=cnt;
	fa[y]=x;
}
inline ll get(int x)
{
	ll ret=0;
	for(int i=head[x];i;i=e[i].next) ret^=get(e[i].to);
	return ret+1;
}
int main()
{
	t=read();
	while (t--)
	{
		cnt=tt=0;
		memset(fa,0,sizeof(fa));
		memset(head,0,sizeof(head));
		n=read();
		F(i,1,n)
		{
			a[i].x=read();a[i].y=read();a[i].r=read();
			q[++tt]=(bor){a[i].x-a[i].r,1,i};
			q[++tt]=(bor){a[i].x+a[i].r,-1,i};
		}
		sort(q+1,q+tt+1);
		F(i,1,tt)
		{
			if (q[i].f==1)
			{
				tmp=q[i].x;
				it=s.lower_bound(pos(q[i].id,1));
				if (it!=s.end())
				{
					if (it->opt==1) add_edge(it->id,q[i].id);
					else if (fa[it->id]) add_edge(fa[it->id],q[i].id);
				}
				s.insert(pos(q[i].id,1));
				s.insert(pos(q[i].id,-1));
			}
			else
			{
				s.erase(pos(q[i].id,1));
				s.erase(pos(q[i].id,-1));
			}
		}
		ll sum=0;
		F(i,1,n) if (!fa[i]) sum=sum^get(i);
		puts(sum?"Alice":"Bob");
	}
}