比赛 26暑假集训模拟赛1 评测结果 AAATTTTTTT
题目名称 光线追踪 最终得分 30
用户昵称 rzzakioi 运行时间 21.720 s
代码语言 C++ 内存使用 4.82 MiB
提交时间 2026-06-29 12:41:17
显示代码纯文本
#include<cstdio>
#include<map>
#include<vector>
//#define int long long
using namespace std;
int q,cnt,ans[100005];
struct node{
    int x0,y0,x1,yy1;
}a[100005];
signed main(){
    freopen("raytracing.in","r",stdin);
    freopen("raytracing.out","w",stdout);
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int op;
        scanf("%d",&op);
        if(op==1){
            ++cnt;
            ans[cnt]=i;
            scanf("%d%d%d%d",&a[cnt].x0,&a[cnt].y0,&a[cnt].x1,&a[cnt].yy1);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==0){
                int x=2e9,id=0;
                for(int j=1;j<=cnt;j++){
                    if(a[j].x0==0&&a[j].y0<x){
                        x=a[j].y0;
                        id=j;
                    }
                }
                printf("%d\n",ans[id]);
            }
            else if(y==0){
                int x=2e9,id=0;
                for(int j=1;j<=cnt;j++){
                    if(a[j].y0==0&&a[j].x0<x){
                        x=a[j].x0;
                        id=j;
                    }
                }
                printf("%d\n",ans[id]);
            }
            else{
                double k=1.0*y/x;
                vector<pair<double,int> >v;
                for(int j=1;j<=cnt;j++){
                    double x,y;
                    x=a[j].x0,y=x*k;
                    if(a[j].y0<=y&&y<=a[j].yy1){
                        v.push_back(make_pair(x,j));
                        continue;
                    }
                    y=a[j].y0,x=y/k;
                    if(a[j].x0<=x&&x<=a[j].x1){
                        v.push_back(make_pair(x,j));
                        continue;
                    }
                }
                double x=2e9;
                int id=0;
                for(int j=0;j<v.size();j++){
                    if(v[j].first<x){
                        x=v[j].first;
                        id=v[j].second;
                    }
                }
                printf("%d\n",ans[id]);
            }
        }
    }
    return 0;
}