思路：
圆扫描线+树上删边博弈
圆扫描线有以下四种情况，用set维护扫描线与圆的交点，重载小于号
代码：
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define y1 y11 #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define pdd pair<double, double> #define mem(a, b) memset(a, b, sizeof(a)) #define debug(x) cerr << #x << " = " << x << " "; const int N = 2e4 + 5; int nowx; struct circle { int x, y, r; }p[N]; double Y(int id, int ty) { if(ty == 0) return p[id].y - sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x)); else return p[id].y + sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x)); } struct node { int id, ty; bool operator < (const node &rhs) const { if(id == rhs.id) return ty < rhs.ty; else return Y(id, ty) < Y(rhs.id, rhs.ty); } }; set<node> s; vector<int> g[N]; int T, n, dp[N], fa[N], sg[N]; piii t[N*2]; void dfs(int u, int o) { sg[u] = 0; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i]; if(v != o) { dfs(v, u); sg[u] ^= sg[v] + 1; } } } int main() { p[0].x = p[0].y = 0; p[0].r = 100000; s.insert({0, 0}); s.insert({0, 1}); scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].r); for (int i = 1; i <= n; ++i) { t[i].fi.fi = p[i].x - p[i].r; t[i].fi.se = 0; t[i].se = i; t[n+i].fi.fi = p[i].x + p[i].r; t[n+i].fi.se = 1; t[n+i].se = i; } sort(t+1, t+1+2*n); for (int i = 1; i <= 2*n; ++i) { nowx = t[i].fi.fi; int id = t[i].se; node tmp = {id, 1}; if(t[i].fi.se == 0) { auto l = s.lower_bound(tmp); --l; auto r = s.upper_bound(tmp); if((*l).id == (*r).id) { dp[id] = dp[(*l).id] + 1; fa[id] = (*l).id; } else if(dp[(*l).id] >= dp[(*r).id]) { dp[id] = dp[(*l).id]; fa[id] = fa[(*l).id]; } else { dp[id] = dp[(*r).id]; fa[id] = fa[(*r).id]; } g[fa[id]].pb(id); s.insert({id, 1}); s.insert({id, 0}); } else { s.erase({id, 1}); s.erase({id, 0}); } } dfs(0, 0); if(sg[0]) printf("Alice "); else printf("Bob "); for (int i = 0; i <= n; ++i) g[i].clear(), sg[i] = fa[i] = dp[i] = 0; } return 0; }