比赛 26暑假集训模拟赛1 评测结果 AAATTTTTTT
题目名称 光线追踪 最终得分 30
用户昵称 赵飞羽 运行时间 21.755 s
代码语言 C++ 内存使用 4.30 MiB
提交时间 2026-06-29 09:54:27
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, op, tot, pos;
double x, y;
struct node1{
	double x_0, y_0, x_1, y_1;
	int idx;
} a[N];
struct node2{
	double xx, yy;
	int idx;
} b[N];

bool cmp(node2 c, node2 d) {
	if (c.xx == d.xx) {
		if (c.yy == d.yy) {
			return c.idx > d.idx;
		}
		return c.yy < d.yy;
	}
	return c.xx < d.xx;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("raytracing.in", "r", stdin);
	freopen("raytracing.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> op;
		if (op == 1) {
			++tot;
			cin >> a[tot].x_0 >> a[tot].y_0 >> a[tot].x_1 >> a[tot].y_1;
			a[tot].idx = i;
		} else if (op == 2) {
			cin >> x >> y;
			for (int j = 1; j <= pos + 10; j++) {
				b[j].xx = 0;
				b[j].yy = 0;
				b[j].idx = 0;
			}
			pos = 0;
			for (int j = tot; j >= 1; j--) {
				double dx = a[j].y_0 * x / (y == 0? -1: y), dy = a[j].y_0;
				double lx = a[j].x_0, ly = a[j].x_0 * y / (x == 0? -1: x);
				if (dx >= a[j].x_0 && dx <= a[j].x_1) {
					++pos;
					b[pos].idx = a[j].idx;
					b[pos].xx = dx;
					b[pos].yy = dy;
				}
				if (ly >= a[j].y_0 && ly <= a[j].y_1) {
					++pos;
					b[pos].idx = a[j].idx;
					b[pos].xx = lx;
					b[pos].yy = ly;
				}
			}
			sort(b+1, b+1+pos, cmp);
			cout << b[1].idx << "\n";
		}
	}
	return 0;
}