「FJOI2013」圆形游戏
题目描述
在一个无穷大的桌面上有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”。
样例输入
|
1 2 3 4 5 6 7 8 9 10 11 |
<span class="sampledata">2 1 0 0 1 6 -100 0 90 -50 0 1 -20 0 1 100 0 90 47 0 1 23 0 1 </span> |
样例输出
|
1 2 |
<span class="sampledata">Alice Bob</span> |
题解
扫描线处理圆的包含关系。。
然后树上删边游戏。。。
但是我发现。。这题每个圆要获得包含它的最小的圆。。。
我只会获得包含它的最大的圆。。
于是我进行了骗分。。在最大的圆的子树中找包含它最小的。。。
于是最后一个点T了
然后我机智的特判了个n<=10000即执行骗分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #define inf 1000000000 #define ll long long #define pa pair<int,int> using namespace std; 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; } int T; int n,cnt,tot; set<pa> t; set<pa>::iterator it; pa a[100005]; int x[50005],y[50005],r[50005],last[50005]; struct edge{int to,next;}e[100005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } inline bool contain(int a,int b) { return (ll)(x[a]-x[b])*(x[a]-x[b])+(ll)(y[a]-y[b])*(y[a]-y[b])<=r[b]*r[b]; } void add(int x,int y) { for(int i=last[x];i;i=e[i].next) if(contain(e[i].to,y)) { add(e[i].to,y); return; } insert(x,y); } void pre() { memset(last,0,sizeof(last)); tot=cnt=0; for(int i=1;i<=n;i++) { a[++tot]=make_pair(x[i]-r[i],i); a[++tot]=make_pair(x[i]+r[i],i+n); } sort(a+1,a+tot+1); for(int i=1;i<=tot;i++) { int now=a[i].second; if(now<=n) { it=t.lower_bound(make_pair(y[now],now)); if(it!=t.end()) if(contain(now,it->second)) { if(n<=10000)add(it->second,now); else insert(it->second,now); continue; } if(it!=t.begin()) if(contain(now,(--it)->second)) { if(n<=10000)add(it->second,now); else insert(it->second,now); continue; } t.insert(make_pair(y[now],now)); insert(n+1,now); } else t.erase(make_pair(y[now-n],now-n)); } } int dfs(int x) { int res=0; for(int i=last[x];i;i=e[i].next) res^=dfs(e[i].to)+1; return res; } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),r[i]=read(); pre(); if(dfs(n+1))puts("Alice"); else puts("Bob"); } return 0; } |
计数器 9319761
OI 课件=>
OI 课件=>
你们OJ上的数据是哪个学长做的
数据有错
圆有交。。。比如第9个点有这两行
-42656 -37409 25922
-42909 -32626 29436
不知道啊
6,7,9,10号点，你问一下
这好早以前的事情了我问谁去。。