NOIp模拟 光线追踪

传送门 这种问题考虑怎么一步一步把问题化简。 首先可以把一个矩形右边和上面的边都丢掉。和那个$speike$有点像。 然后可以把剩下的横边和竖边独立开来看。如果可以分别求出询问向量所碰到的横和竖的最短距离问题就解决了。取最小距离即可。 对于插入的横/竖边，在对应的角度区间里面更新一下最小的横/纵坐标以及对应的编号即可。 查询碰到的最近的竖/横边就是单点查询最小值。

于是把角度离散化一下就可以用线段树维护了。 坐标相同的时候取编号大的，这个用$pair$很好做。 区间修改采用标记永久化的方法做会很方便，不能$pushup$。

询问的时候要特判一下$x=0ory=0$。

#include<bits/stdc++.h> #define ll long long #define re register #define cs const #define pii std::pair<int,int> #define mp std::make_pair #define fi first #define se second cs int N=1e5+10,oo=1e9+1; namespace IO{ cs int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;} template<typename T> inline T get(){ char ch=gc();T x=0; while(!isdigit(ch)) ch=gc(); while(isdigit(ch)) x=(x+(x<<2)<<1)+(ch^48),ch=gc(); return x; } inline int gi(){return get<int>();} } using IO::gi; struct Point{ int x,y; inline double k(){return x?1.0*y/x:1e18;} }; struct OP{int op,dk[3];Point P[3];double k[3];}a[N]; int Q,M;double st[N*3];int top=0; inline void disc(){ std::sort(st+1,st+top+1); M=std::unique(st+1,st+top+1)-st-1; for(int re i=1;i<=Q;++i) for(int re j=0;j<3;++j) a[i].dk[j]=std::lower_bound(st+1,st+M+1,a[i].k[j])-st; } #define mid (T[root].l+T[root].r>>1) #define lc (root<<1) #define rc (root<<1|1) struct node{int l,r;pii h;}; inline pii pmin(cs pii &p,cs pii &q){ return (p.fi==q.fi)?(p.se>q.se?p:q):(p.fi<q.fi?p:q); } inline void pMin(pii &p,cs pii &q){ p=(p.fi==q.fi)?(p.se>q.se?p:q):(p.fi<q.fi?p:q);; } struct SGT{ node T[(N*3)<<2]; inline void build(int root,int l,int r){ T[root].l=l,T[root].r=r,T[root].h=mp(oo,0); if(l==r) return; build(lc,l,mid),build(rc,mid+1,r); } inline void insert(int root,int l,int r,cs pii &now){ if(l<=T[root].l&&T[root].r<=r) return pMin(T[root].h,now); if(l> mid) return insert(rc,l,r,now); if(r<=mid) return insert(lc,l,r,now); return insert(lc,l,mid,now),insert(rc,mid+1,r,now); } inline pii query(int root,int pos){ if(T[root].l==T[root].r) return T[root].h; return pmin(T[root].h,(pos<=mid)?query(lc,pos):query(rc,pos)); } }TREE[2]; #undef mid #undef lc #undef rc int main(){ // freopen("raytracing.in","r",stdin); Q=gi(); for(int re i=1;i<=Q;++i){ a[i].op=gi(); if(a[i].op==1) a[i].P[0].x=a[i].P[1].x=gi(), a[i].P[0].y=a[i].P[2].y=gi(), a[i].P[2].x=gi(),a[i].P[1].y=gi(), st[++top]=a[i].k[0]=a[i].P[0].k(),st[++top]=a[i].k[1]=a[i].P[1].k(),st[++top]=a[i].k[2]=a[i].P[2].k(); if(a[i].op==2) a[i].P[0].x=gi(),a[i].P[0].y=gi(),st[++top]=a[i].k[0]=a[i].P[0].k(); }disc(),TREE[0].build(1,1,M),TREE[1].build(1,1,M); for(int re i=1;i<=Q;++i){ if(a[i].op==1){ TREE[0].insert(1,a[i].dk[0],a[i].dk[1],mp(a[i].P[0].x,i)); TREE[1].insert(1,a[i].dk[2],a[i].dk[0],mp(a[i].P[0].y,i)); } if(a[i].op==2){ pii q0=TREE[0].query(1,a[i].dk[0]),q1=TREE[1].query(1,a[i].dk[0]); if(!(q0.se+q1.se)) puts("0"); else if(!q0.se||!q1.se) printf("%d\n",q0.se+q1.se); else if(a[i].P[0].y==0) printf("%d\n",q0.fi<a[q1.se].P[0].x?q0.se:q1.se); else if(a[i].P[0].x==0) printf("%d\n",q1.fi<a[q0.se].P[0].y?q1.se:q0.se); else{ ll mul1=1ll*q1.fi*a[i].P[0].x,mul0=1ll*q0.fi*a[i].P[0].y; printf("%d\n",(mul1==mul0)?(q0.se>q1.se?q0.se:q1.se):(mul1>mul0?q0.se:q1.se)); } } } }