萌新代码求条
查看原帖
萌新代码求条
761491
Zzzcr楼主2024/12/26 23:58

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.
2024/12/26 23:58
加载中...