比赛 26暑假集训模拟赛1 评测结果 AAATTTTTTT
题目名称 光线追踪 最终得分 30
用户昵称 对立猫猫对立 运行时间 22.000 s
代码语言 C++ 内存使用 4.21 MiB
提交时间 2026-06-29 11:08:19
显示代码纯文本
#include <bits/stdc++.h>
#define MAXN 100000
#define int long long
#define pii pair<int, int>
using namespace std;
//struct sgt {
//    struct Node {
//        int ls = 0, rs = 0;
//        int tag = 0;
//        int sum = 0;
//    };
//    vector<Node> tr;
//    int cnt;
//    void build(int n) {
//        tr.clear();
//        tr.resize(n * 4);
//        cnt = 1;
//    }
//    void pushup(int p, int l, int r) {
//        if (tr[p].tag) {
//            tr[p].sum = y[r] - y[l - 1];
//        } else if (l == r) {
//            tr[p].sum = 0;
//        } else {
//            tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum;
//        }
//    }
//    void update(int p, int l, int r, int ql, int qr, int val) {
//        if (ql <= l && r <= qr) {
//            tr[p].tag += val;
//            pushup(p, l, r);
//            return;
//        }
//        int mid = (l + r) >> 1;
//        if (ql <= mid) {
//            if (!tr[p].ls) tr[p].ls = ++cnt;
//            update(tr[p].ls, l, mid, ql, qr, val);
//        }
//        if (qr > mid) {
//            if (!tr[p].rs) tr[p].rs = ++cnt;
//            update(tr[p].rs, mid + 1, r, ql, qr, val);
//        }
//        pushup(p, l, r);
//    }
//} xgt;
//struct smx {
//    int id, x, y0, y1, val;
//    bool operator<(const smx a) {
//        return x < a.x;
//    }
//};
struct fs {
    int p, q;
    bool operator<=(const fs a) {
        int tf = q / __gcd(q, a.q) * a.q;
        return p * (tf / q) <= a.p * (tf / a.q);
    }
};
struct point {
    double x, y;
    bool operator<(const point a) {
        return sqrt(x * x + y * y) < sqrt(a.x * a.x + a.y * a.y);
    }
    bool operator!=(const point a) {
        return (abs(x - a.x + y - a.y) > 0.01);
    }
};
fs hj(fs a) {
    if(a.p == 0) return {0, 1};
    if(a.q == 0) return {1000000000000, 1};
    int m = __gcd(a.p, a.q);
    return {a.p / m, a.q / m};
}
//vector<smx> v;
//vector<int> ally;
vector<pair<int, pair<fs, fs>>> forbid;
//void work() {
//    sort(v.begin(), v.end());
//    sort(ally.begin(), ally.end());
//    ally.erase(unique(ally.begin(), ally.end()), y.end());
//    int m = y.size();
//    xgt.build(m);
//    for(int i = 0; i < v.size(); i++) {
//        
//    }
//}
int Q, op;
int sx[100005], sy[100005], ex[100005], ey[100005];
bool canx = 1, cany = 1;
vector<pair<fs, pii>> poss;
bool cmp(pair<fs, pii> a, pair<fs, pii> b) {
    point m, n;
    if(a.second.second == 1) {
        m.y = sy[a.second.first];
        m.x = m.y * a.first.q / a.first.p;
    }
    else {
        m.x = sx[a.second.first];
        m.y = m.x * a.first.p / a.first.q;
    }
    if(b.second.second == 1) {
        n.y = sy[b.second.first];
        n.x = n.y * b.first.q / b.first.p;
    }
    else {
        n.x = sx[b.second.first];
        n.y = n.x * b.first.p / b.first.q;
    }
    if(m != n) return m < n;
    else return a.second.first > b.second.first;
}
int query(fs tangnt) {
    poss.clear();
    for(int i = 0; i < forbid.size(); i++) {
        if(tangnt <= forbid[i].second.first && forbid[i].second.second <= tangnt) poss.push_back({tangnt, {forbid[i].first, tangnt <= hj({sy[forbid[i].first], sx[forbid[i].first]}) ? 1 : 0}});
    }
    if(poss.empty()) return 0;
    sort(poss.begin(), poss.end(), cmp);
//    for(int i = 0; i < poss.size(); i++) {
//        cout << poss[i] << " ";
//    }
//    cout << endl;
    return poss[0].second.first;
}
signed main() {
    freopen("raytracing.in", "r", stdin);
    freopen("raytracing.out", "w", stdout);
    cin >> Q;
    for(int i = 1; i <= Q; i++) {
        cin >> op;
        if(op == 1) {
            cin >> sx[i] >> sy[i] >> ex[i] >> ey[i];
            if(sx[i] == 0) cany = 0;
            if(sy[i] == 0) canx = 0;
            forbid.push_back({i, make_pair(hj({ey[i], sx[i]}), hj({sy[i], ex[i]}))});
        }
        else {
//            for(int i = 0; i < forbid.size(); i++) {
//                cout << forbid[i].second.first.p << "/" << forbid[i].second.first.q;
//                cout << " " << forbid[i].second.second.p << "/" << forbid[i].second.second.q << endl;
//            }
            int qx, qy;
            cin >> qx >> qy;
            if(qx == 0 && cany == 1) cout << 0 << endl;
            else if(qy == 0 && canx == 1) cout << 0 << endl;
            else {
                cout << query(hj({qy, qx})) << endl;
            }
        }
    }
    return 0;
}