Untitled
unknown
c_cpp
2 years ago
5.0 kB
12
Indexable
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif
using ll = long long;
using db = long double;
template <typename T>
struct point {
T x, y;
point() {
x = 0;
y = 0;
}
point(const T &_x, const T &_y) {
x = _x;
y = _y;
}
point(const point &a, const point &b) {
x = b.x - a.x;
y = b.y - a.y;
}
point operator+(const point &other) {
return point(x + other.x, y + other.y);
}
point operator-(const point &other) {
return point(x - other.x, y - other.y);
}
T operator*(const point &other) {
return x * other.x + y * other.y;
}
T operator%(const point &other) {
return x * other.y - other.x * y;
}
};
template <typename T>
istream& operator>>(istream& in, point<T> &p) {
in >> p.x >> p.y;
return in;
}
using pt = point<ll>;
db PolarAngle(pt p) {
return atan2((db)p.y, (db)p.x);
}
bool cmp(pt a, pt b) {
return PolarAngle(a) < PolarAngle(b);
}
constexpr int N = 1e4;
int grundy[N + 1];
void calc() {
grundy[0] = 0;
for (int i = 1; i <= N; i++) {
bitset<1000> used;
used[grundy[i - 1]] = 1;
for (int j = 0; 2 * j <= i - 2; j++) {
used[grundy[j] ^ grundy[i - 2 - j]] = 1;
}
grundy[i] = 0;
while (used[grundy[i]]) {
grundy[i]++;
}
}
}
struct segtree {
struct node {
int pref, suf, gr, sz;
};
node combine(node a, node b) {
if (b.sz == 0) return a;
int pref = a.pref;
if (a.pref == a.sz) {
pref = a.pref + b.pref;
}
int suf = b.suf;
if (b.suf == b.sz) {
suf = b.suf + a.suf;
}
int gr = a.gr ^ b.gr;
if (a.suf != a.sz && b.pref != b.sz) {
gr ^= grundy[a.suf + b.pref];
}
return {
pref,
suf,
gr,
a.sz + b.sz
};
}
node one_element(int x) {
return {
x,
x,
0,
1
};
}
int size;
vector<node> tree;
void init(int n) {
size = 1;
while (size < n) size *= 2;
tree.assign(2 * size - 1, {0, 0, 0, 0});
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = one_element(v);
} else {
int m = (lx + rx) / 2;
if (i < m) {
set(i, v, x * 2 + 1, lx, m);
} else {
set(i, v, x * 2 + 2, m, rx);
}
tree[x] = combine(tree[x * 2 + 1], tree[x * 2 + 2]);
}
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int get() {
int res = tree[0].gr;
if (tree[0].pref == tree[0].sz) {
return (grundy[tree[0].sz - 2] == 0 ? 1 : 0);
}
res ^= grundy[tree[0].pref + tree[0].suf];
return res;
}
};
void test_case() {
calc();
int n, m, q;
cin >> n >> m >> q;
pt C;
cin >> C;
vector<pt> pts(n);
for (int i = 0; i < n; i++) {
cin >> pts[i];
pts[i] = pts[i] - C;
}
sort(pts.begin(), pts.end(), cmp);
segtree tr;
tr.init(n);
for (int i = 0; i < n; i++) {
tr.set(i, 0);
}
vector<int> cnt(n);
auto add = [&](db pa, int x) -> void {
if (pa < PolarAngle(pts[0])) {
cnt[n - 1] += x;
if (cnt[n - 1] == 0 && x == -1) {
tr.set(n - 1, 0);
}
if (cnt[n - 1] == 1) {
tr.set(n - 1, 1);
}
return;
}
int L = 0, R = n;
while (L + 1 != R) {
int M = (L + R) / 2;
if (PolarAngle(pts[M]) <= pa) {
L = M;
} else {
R = M;
}
}
cnt[L] += x;
if (cnt[L] == 0 && x == -1) {
tr.set(L, 0);
}
if (cnt[L] == 1) {
tr.set(L, 1);
}
};
for (int i = 0; i < m; i++) {
pt M;
cin >> M;
M = M - C;
add(PolarAngle(M), 1);
}
cout << (tr.get() != 0 ? "Alice\n" : "Bob\n");
while (q--) {
char t;
cin >> t;
pt M;
cin >> M;
M = M - C;
if (t == '+') {
add(PolarAngle(M), 1);
} else {
add(PolarAngle(M), -1);
}
cout << (tr.get() != 0 ? "Alice\n" : "Bob\n");
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int tests = 1;
// cin >> tests;
while (tests--) {
test_case();
}
return 0;
}Editor is loading...
Leave a Comment