fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef double dbl;
  5.  
  6. const dbl EPS = 1e-8;
  7. int sgn(dbl a) { return (a > EPS) - (a < -EPS); }
  8. int sgn(dbl a, dbl b) { return sgn(a-b); }
  9.  
  10. template <typename T> T sq(T a) { return a*a; }
  11.  
  12. const int MAXN = 2.1e4;
  13.  
  14. int curX;
  15.  
  16. struct circle {
  17.     int a, b, r;
  18.  
  19.     circle() {}
  20.  
  21.     circle(int a_, int b_, int r_) : a(a_), b(b_), r(r_) {}
  22.  
  23.     dbl get_y(int t) {
  24.         dbl y = t * sqrt(sq(r) - sq(curX-a)) + b;
  25.         return y;
  26.     }
  27. } circs[MAXN];
  28.  
  29. struct event {
  30.     int x, ind;
  31.  
  32.     event() {}
  33.  
  34.     event(int x_, int ind_) : x(x_), ind(ind_) {}
  35.  
  36.     bool operator < (const event& o) const {
  37.         return make_pair(x, ind) < make_pair(o.x, o.ind);
  38.     }
  39. };
  40.  
  41. int sgn(int i) { return (i >= 0) - (i < 0); }
  42. int realind(int i) { return max(i, ~i); }
  43.  
  44. struct cmp {
  45.     bool operator () (int i, int j) const {
  46.         dbl yi = circs[realind(i)].get_y(sgn(i));
  47.         dbl yj = circs[realind(j)].get_y(sgn(j));
  48.         int s = sgn(yi, yj);
  49.         if (s == 0) {
  50.             return i < j;
  51.         } else {
  52. 			return s < 0;
  53.         }
  54.     }
  55. };
  56.  
  57. vector<int> adj[MAXN];
  58. int depth[MAXN];
  59. int par[MAXN];
  60.  
  61. int dfs_grundy(int cur) {
  62.     int res = 0;
  63.     for (int z = 0; z < int(adj[cur].size()); z++) {
  64.         int nxt = adj[cur][z];
  65.         res ^= dfs_grundy(nxt)+1;
  66.     }
  67.     return res;
  68. }
  69.  
  70. bool go() {
  71.     int N; cin >> N;
  72.  
  73.     circs[0] = circle(0, 0, int(4.1e4));
  74.     N++;
  75.     for (int i = 1; i < N; i++) {
  76.         int a, b, r; cin >> a >> b >> r;
  77.         circs[i] = circle(a, b, r);
  78.     }
  79.  
  80.     vector<event> evts; evts.reserve(2*N);
  81.     for (int i = 0; i < N; i++) {
  82.         int a = circs[i].a;
  83.         int r = circs[i].r;
  84.         evts.push_back(event(a-r, i));
  85.         evts.push_back(event(a+r, ~i));
  86.     }
  87.     sort(evts.begin(), evts.end());
  88.  
  89.     for (int i = 0; i < N; i++) {
  90.         adj[i].clear();
  91.         depth[i] = -1;
  92.         par[i] = -1;
  93.     }
  94.     depth[0] = 0;
  95.  
  96.     set<int, cmp> arcs;
  97.     for (int z = 0; z < 2*N; z++) {
  98.         event& evt = evts[z];
  99.         curX = evt.x;
  100.         int i = evt.ind;
  101.  
  102.         if (i < 0) {
  103.             arcs.erase(i);
  104.             arcs.erase(~i);
  105.         } else {
  106.             set<int, cmp>::iterator hi = arcs.lower_bound(i);
  107.             set<int, cmp>::iterator lo = hi;
  108.             if (hi == arcs.end() || lo == arcs.begin()) {
  109. 				// root
  110.             } else {
  111.                 --lo;
  112.  
  113.                 int ilo = realind(*lo);
  114.                 int ihi = realind(*hi);
  115.                 if (ilo == ihi) {
  116.                     adj[ilo].push_back(i);
  117.                     depth[i] = depth[ilo]+1;
  118.                     par[i] = ilo;
  119.                 } else {
  120.                     if (depth[ilo] > depth[ihi]) swap(ilo, ihi);
  121. 					adj[par[ihi]].push_back(i);
  122.                     depth[i] = depth[par[ihi]]+1;
  123.                     par[i] = par[ihi];
  124.                 }
  125.             }
  126.  
  127.             arcs.insert(i);
  128.             arcs.insert(~i);
  129.         }
  130.     }
  131.  
  132.     return bool(dfs_grundy(0));
  133. }
  134.  
  135. int main() {
  136.     ios::sync_with_stdio(0), cin.tie(0);
  137.  
  138.     int T; cin >> T;
  139.     while (T--) {
  140.         cout << (go() ? "Alice" : "Bob") << '\n';
  141.     }
  142.  
  143.     return 0;
  144. }
  145.  
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
2
1
0 0 1
6
-100 0 90
-50 0 1
-20 0 1
100 0 90
47 0 1
23 0 1
stdout
copy 
Alice
Bob
https://ideone.com/eijX0R
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!