| 比赛 |
26暑假集训模拟赛1 |
评测结果 |
AAAWWWEEEE |
| 题目名称 |
光线追踪 |
最终得分 |
30 |
| 用户昵称 |
exil |
运行时间 |
2.398 s |
| 代码语言 |
C++ |
内存使用 |
13.44 MiB |
| 提交时间 |
2026-06-29 12:00:37 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int sum;
int l;
int r;
int lan;
};
node tree[405][1205];
void jianshu(int shu,int k,int l,int r){
tree[shu][k]={0,l,r,0};
if(l==r){
return;
}
int mid=(l+r)/2;
jianshu(shu,k<<1,l,mid);
jianshu(shu,k<<1|1,mid+1,r);
}
void pushdown(int shu,int x){
if(tree[shu][x].lan==0)return;
tree[shu][x<<1].lan=tree[shu][x].lan;
tree[shu][x<<1|1].lan=tree[shu][x].lan;
tree[shu][x<<1].sum=(tree[shu][x<<1].r-tree[shu][x<<1].l+1)*tree[shu][x].lan;
tree[shu][x<<1|1].sum=(tree[shu][x<<1|1].r-tree[shu][x<<1|1].l+1)*tree[shu][x].lan;
tree[shu][x].lan=0;
}
void add(int shu,int k,int l,int r,int v){
if(tree[shu][k].l>r || tree[shu][k].r<l)return;
pushdown(shu,k);
if(tree[shu][k].l>=l && tree[shu][k].r<=r){
tree[shu][k].lan=v;
tree[shu][k].sum=(tree[shu][k].r-tree[shu][k].l+1)*v;
return;
}
add(shu,k<<1,l,r,v);
add(shu,k<<1|1,l,r,v);
tree[shu][k].sum=tree[shu][k<<1].sum+tree[shu][k<<1|1].sum;
}
int cha(int shu,int k,int wei){
if(tree[shu][k].l>wei || tree[shu][k].r<wei)return 0;
pushdown(shu,k);
if(tree[shu][k].l==wei && tree[shu][k].r==wei){
return tree[shu][k].sum;
}
return cha(shu,k<<1,wei) + cha(shu,k<<1|1,wei);
}
signed main(){
freopen("raytracing.in","r",stdin);
freopen("raytracing.out","w",stdout);
int q;
cin>>q;
if(q<=1000){
vector<double> v[5];
for(int i = 1;i<=q;i++){
int s;
cin>>s;
if(s==1){
double x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
v[1].push_back(x1),v[2].push_back(y1),v[3].push_back(x2),v[4].push_back(y2);
v[0].push_back(i);
}
else if(s==2){
double x,y;
cin>>x>>y;
int len=v[1].size();
double minn=INT_MAX,r=0;
for(int j = len-1;j>=0;j--){
//下边
double xx=v[2][j]/y*x;
if(v[1][j]<=xx && v[3][j]>=xx){
if(xx<minn){
minn=xx;
r=v[0][j];
}
continue;
}
//左边
double yy=v[1][j]/x*y;
if(v[2][j]<=yy && v[4][j]>=yy){
if(v[1][j]<minn){
minn=v[1][j];
r=v[0][j];
}
continue;
}
}
cout<<r<<endl;
}
}
return 0;
}
for(int i = 1;i<=402;i++){
jianshu(i,1,0,200);
}
for(int i = 1;i<=q;i++){
int s;
cin>>s;
if(s==1){
double x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
add(y1,1,x1,x2,i);
add(x1+201,1,y1,y2,i);
}
else if(s==2){
double x,y;
cin>>x>>y;
double minn=INT_MAX;
int r=0;
for(int j = 1;j<=200;j++){
double xx=j/y*x;
int xx1=xx;
if(xx1==xx){
int e=cha(j,1,xx1);
if(e!=0){
if(xx<minn){
r=e;
minn=min(minn,xx);
}
else if(xx==minn)r=max(r,e);
break;
}
}
else{
int e1=cha(j,1,xx1),e2=cha(j,1,xx1+1);
if(e1!=0 && e2!=0){
if(xx<minn){
r=min(e1,e2);
//cout<<e1<<" "<<e2<<endl;
minn=min(minn,xx);
}
else if(xx==minn)r=max(r,min(e1,e2));
break;
}
}
}
for(int j = 201;j<=400;j++){
double yy=(j-200)/x*y;
int yy1=yy;
double tt=j-200;
if(yy1==yy){
int e=cha(j,1,yy1);
if(e!=0){
if(tt<minn){
r=e;
minn=min(minn,tt);
}
else if(tt==minn)r=max(r,e);
break;
}
}
else{
int e1=cha(j,1,yy1),e2=cha(j,1,yy1+1);
if(e1!=0 && e2!=0){
if(tt<minn){
r=min(e1,e2);
//cout<<"ee"<<r<<endl;
minn=min(minn,tt);
}
else if(tt==minn)r=max(r,min(e1,e2));
break;
}
}
}
cout<<r<<endl;
}
}
return 0;
}