Untitled

 avatar
unknown
c_cpp
a year ago
5.0 kB
5
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