题解 (by;zjvarphi)
一个矩形，它的贡献只能在它的左边界或它的下边界，意思就是，一条射线和它的第一个交点一定在它的左边界或它的下边界
而一个矩形能截到的直线的斜率在 ([frac{y}{x_1},frac{y_1}{x}]) ，所以对于左边界的斜率范围，和下边界的斜率范围，分别建一棵线段树。
有小数范围，不能直接建在值域上，所以要离散化，为了防止暴精度，分数比大小用对角线乘法。
Code
#include<bits/stdc++.h>
#define ri signed
#define pd(i) ++i
#define bq(i) --i
#define func(x) std::function<x>
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
#define debug1(x) std::cerr << #x"=" << x << ' '
#define debug2(x) std::cerr << #x"=" << x << std::endl
#define Debug(x) assert(x)
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
bool f=false;x=0;char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
using LL=long long;
static const int N=1e5+7,INF=1061109567;
int ll[N],ml[N],rl[N],id[N],q,cnt;
struct Que{int opt,x,y,xx,yy;}que[N];
struct node{int w,id;};
struct Node{int x,y;}pnt[N<<2];
inline bool operator<(const Node &n1,const Node &n2) {return 1ll*n1.y*n2.x<1ll*n2.y*n1.x;}
inline bool operator==(const Node &n1,const Node &n2) {return 1ll*n1.y*n2.x==1ll*n2.y*n1.x;}
struct Seg{
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct segmenttree{node id;bool lz;}T[N<<4];
func(void(int)) down=[&](int x) {
if (!T[x].lz) return;
if (!T[ls(x)].id.id) T[ls(x)].id=T[x].id,T[ls(x)].lz=true;
else if (T[x].id.w<=T[ls(x)].id.w) T[ls(x)].id=T[x].id,T[ls(x)].lz=true;
if (!T[rs(x)].id.id) T[rs(x)].id=T[x].id,T[rs(x)].lz=true;
else if (T[x].id.w<=T[rs(x)].id.w) T[rs(x)].id=T[x].id,T[rs(x)].lz=true;
T[x].lz=false;
};
func(void(int,int,int)) build=[&](int x,int l,int r) {
T[x].id={INF,0};
if (l==r) return;
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
};
func(void(int,node,int,int,int,int)) update=[&](int x,node k,int l,int r,int lt,int rt) {
if (l<=lt&&rt<=r) {
if (T[x].id.w>=k.w) T[x].id=k,T[x].lz=true;
return;
}
int mid=(lt+rt)>>1;
down(x);
if (l<=mid) update(ls(x),k,l,r,lt,mid);
if (r>mid) update(rs(x),k,l,r,mid+1,rt);
};
func(node(int,int,int,int)) query=[&](int x,int p,int l,int r) {
if (l==r) return T[x].id;
int mid=(l+r)>>1;
down(x);
if (p<=mid) return query(ls(x),p,l,mid);
else return query(rs(x),p,mid+1,r);
};
}T,S;
inline int main() {
FI=freopen("raytracing.in","r",stdin);
FO=freopen("raytracing.out","w",stdout);
cin >> q;
for (ri i(1);i<=q;pd(i)) {
cin >> que[i].opt;
if (que[i].opt==1) {
cin >> que[i].x >> que[i].y >> que[i].xx >> que[i].yy;
pnt[++cnt]={que[i].x,que[i].y};
pnt[++cnt]={que[i].x,que[i].yy};
pnt[++cnt]={que[i].xx,que[i].y};
} else {
cin >> que[i].x >> que[i].y;
pnt[++cnt]={que[i].x,que[i].y};
}
}
std::sort(pnt+1,pnt+cnt+1);
int k=std::unique(pnt+1,pnt+cnt+1)-pnt;
cnt=k-1;
T.build(1,1,cnt),S.build(1,1,cnt);
for (ri i(1);i<=q;pd(i))
if (que[i].opt==1) {
ll[i]=std::lower_bound(pnt+1,pnt+k,(Node){que[i].xx,que[i].y})-pnt;
ml[i]=std::lower_bound(pnt+1,pnt+k,(Node){que[i].x,que[i].y})-pnt;
rl[i]=std::lower_bound(pnt+1,pnt+k,(Node){que[i].x,que[i].yy})-pnt;
} else id[i]=std::lower_bound(pnt+1,pnt+k,(Node){que[i].x,que[i].y})-pnt;
for (ri i(1);i<=q;pd(i))
if (que[i].opt==1) {
T.update(1,{que[i].x,i},ml[i],rl[i],1,cnt);
S.update(1,{que[i].y,i},ll[i],ml[i],1,cnt);
} else {
node ansx=T.query(1,id[i],1,cnt);
node ansy=S.query(1,id[i],1,cnt);
if (!ansx.id||!ansy.id) printf("%d
",ansx.id|ansy.id);
else {
if (!que[i].y) printf("%d
",que[ansy.id].x<ansx.w?ansy.id:ansx.id);
else if (!que[i].x) printf("%d
",que[ansx.id].y<ansy.w?ansx.id:ansy.id);
else {
LL k1=1ll*ansx.w*que[i].y,k2=1ll*que[i].x*ansy.w;
if (k1==k2) printf("%d
",cmax(ansx.id,ansy.id));
else printf("%d
",k1<k2?ansx.id:ansy.id);
}
}
}
return 0;
}
}
int main() {return nanfeng::main();}