| 比赛 |
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;
}