RT, wa on #5.
#include <bits/stdc++.h>
using namespace std;
#define _f(i, a, b) for (int i = a; i <= b; ++i)
constexpr int N = 5e4 + 5, M = 3e6 + 5, inf = 1e9;
constexpr double eps = 1e-9;
mt19937 rnd(time(0));
struct point {
int x, y;
point () { x = y = 0; }
point (int _x, int _y) { x = _x, y = _y; }
bool operator < (point A) const {
return x != A.x ? x < A.x : y < A.y;
}
} p[N];
struct line {
point a, b;
line () {}
line (point _a, point _b) { if(_a < _b) a = _a, b = _b; else a = _b, b = _a; }
inline double val(int x) {
return 1.L * (b.y - a.y) * (x - a.x) / (b.x - a.x) + a.y;
}
bool operator < (point &rhs) {
return val(rhs.x) + eps < 1. * rhs.y;
}
bool operator < (line &rhs) {
int l = max(a.x, rhs.a.x), r = min(b.x, rhs.b.x);
return val(l) + eps < rhs.val(l) || val(r) + eps < rhs.val(r);
}
bool operator == (point &rhs) {
return val(rhs.x) - 1. * rhs.y <= eps;
}
} ;
struct node {
int pri, ls, rs, sz;
line val;
} q[M];
int cnt, lstx, lsty, n, zx[3][2], ans, m;
stack<int> st;
map<point, bool> mp;
struct treap {
int rt;
treap() { rt = 0; }
inline int new_node(line x) {
int qwq;
if(st.size()) qwq = st.top(), st.pop();
else qwq = ++cnt;
q[qwq] = {(int)rnd(), 0, 0, 1, x};
return qwq;
}
inline void pushup(int p) { q[p].sz = q[q[p].ls].sz + q[q[p].rs].sz + 1; }
inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(q[x].pri < q[y].pri) {
q[x].rs = merge(q[x].rs, y);
return pushup(x), x;
} else {
q[y].ls = merge(x, q[y].ls);
return pushup(y), y;
}
}
void split(int p, point k, int &x, int &y) {
if(!p) x = y = 0;
else {
if(q[p].val < k) x = p, split(q[x].rs, k, q[x].rs, y);
else y = p, split(q[p].ls, k, x, q[y].ls);
pushup(p);
}
}
void split(int p, line k, int &x, int &y) {
if(!p) x = y = 0;
else {
if(q[p].val < k) x = p, split(q[x].rs, k, q[x].rs, y);
else y = p, split(q[p].ls, k, x, q[y].ls);
pushup(p);
}
}
void split(int p, int k, int &x, int &y) {
if(!p) x = y = 0;
else {
if(k <= q[q[p].ls].sz) y = p, split(q[p].ls, k, x, q[y].ls);
else x = p, split(q[p].rs, k - q[q[p].ls].sz - 1, q[x].rs, y);
pushup(p);
}
}
void insert(line x) {
int a, b;
split(rt, x, a, b);
rt = merge(merge(a, new_node(x)), b);
}
void remove(line x) {
int a, b, c;
split(rt, x, a, b), split(b, 1, b, c);
rt = merge(a, c), st.emplace(b);
}
int query(point k) {
int a, b, c, ans = 0;
split(rt, k, a, b), c = b, ans = q[b].sz;
while(q[c].ls) c = q[c].ls;
if(q[c].val == k) ans += 1e7;
return rt = merge(a, b), ans;
}
} ;
namespace segT {
struct node {
int ls, rs;
treap T;
} tr[M];
int cnt = 0, rt = 0;
void insert(int &p, int l, int r, line k) {
if(!p) p = ++cnt;
if(k.a.x <= l && r <= k.b.x) return tr[p].T.insert(k), void();
int mid = (l + r) >> 1;
if(k.a.x <= mid) insert(tr[p].ls, l, mid, k);
if(k.b.x > mid) insert(tr[p].rs, mid + 1, r, k);
}
void remove(int &p, int l, int r, line k) {
if(!p) p = ++cnt;
if(k.a.x <= l && r <= k.b.x) return tr[p].T.remove(k), void();
int mid = (l + r) >> 1;
if(k.a.x <= mid) remove(tr[p].ls, l, mid, k);
if(k.b.x > mid) remove(tr[p].rs, mid + 1, r, k);
}
int query(int p, int l, int r, point k) {
if(!p) return 0;
if(l == r) return tr[p].T.query(k);
int mid = (l + r) >> 1, ret = tr[p].T.query(k);
if(ret > 1e7) return ret;
if(k.x <= mid) ret += query(tr[p].ls, l, mid, k);
else ret += query(tr[p].rs, mid + 1, r, k);
return ret;
}
} ;
using segT::rt;
string str[] = {"in", "out", "bd"};
inline line qwq(line x) { return {x.a, {x.b.x - 1, x.b.y}}; }
inline void insert(line x) { segT::insert(rt, 0, inf, qwq(x)); }
inline void remove(line x) { segT::remove(rt, 0, inf, qwq(x)); }
void solve() {
cin >> n;
_f(i, 1, n) cin >> p[i].x >> p[i].y, mp[p[i]] = 1;
_f(i, 1, n) insert({p[i], p[i % n + 1]});
cin >> m, ans = 1 + mp.count(point(0, 0));
while(m--) {
int op, r; cin >> op;
point a, b, c;
if(!op) {
cin >> r;
_f(i, 0, 2) cin >> zx[i][0] >> zx[i][1];
lstx = (1ll * lstx * r + zx[ans][0]) % inf;
lsty = (1ll * lsty * r + zx[ans][1]) % inf;
if(mp.count(point(lstx, lsty))) ans = 2;
else {
int ret = segT::query(rt, 0, inf, point(lstx, lsty));
ret >= 1e7 ? ans = 2 : ans = (ret & 1) ^ 1;
}
cout << str[ans] << '\n';
} else {
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
remove({a, b}), insert({a, c}), insert({b, c}), mp[c] = 1;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
// by zzzcr.