2018.10.26-dtoj-3994-光线追踪（raytracing）
题目描述：
考虑一个二维平面，摄像机在(0,0)的位置，初始时平面上没有障碍物。现在执行𝑄次操作，操作有两种（假设这是第𝑖次操作，1≤𝑖≤𝑄）：
1. 给定𝑥0,𝑦0,𝑥1,𝑦1(𝑥0<𝑥1,𝑦0<𝑦1)，创建一个每条边与坐标轴平行的长方形障碍物，包含所有满足𝑥0≤𝑥≤𝑥1且𝑦0≤𝑦≤𝑦1的点(𝑥,𝑦)（如果这个区域的某一部分已经存在障碍，则直接覆盖掉它，具体请看样例）。这个障碍物的编号为𝑖。
2. 给定向量(𝑥,𝑦)，会有一个动点从摄像机所在的(0,0)位置出发，以(𝑥,𝑦)所指的方向前进，直到碰到第一个障碍物为止。
对于第2种操作，输出最先碰到的障碍物的编号。若不会碰到任何障碍物，输出0。
输入：
输入文件第一行一个正整数Q，表示操作总数。
接下来的Q行，每行第一个正整数𝑜𝑝𝑖为操作种类（保证为1或2）。如果为1，则接下来四个正整数𝑥0,𝑦0,𝑥1,𝑦1(𝑥0<𝑥1,𝑦0<𝑦1)表示障碍的位置；如果为2，则接下来两个正整数𝑥,𝑦表示前进方向。
输出：
输出文件包含𝑅行（𝑅为第2种操作的总数），每行一个正整数，表示第一个碰到的障碍物编号。
数据范围：
对于30% 的数据：𝑄≤1000。
对于另外30% 的数据：0≤𝑥0,𝑦0,𝑥1,𝑦1,𝑥,𝑦≤200。
对于100% 的数据：𝑄≤105，0≤𝑥0,𝑦0,𝑥1,𝑦1,𝑥,𝑦≤109，𝑥0<𝑥1，𝑦0<𝑦1；𝑥0和𝑦0不全为0，𝑥和𝑦不全为0。
算法标签：线段树
思路：
这类题很容易考场一眼线段树，但是具体写真的很难呀...结果测试结束连暴力都没来得及交上去哭了...这题可以存下斜率(要开long double)，然后离散化，存入线段树，考场有一点没想清楚，这棵线段树不需要update和pushup每次单点查询，在线段树每一层都查询答案即可。
以下代码：
#include<bits/stdc++.h> #define il inline #define D long double #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5;const D inf=1e9+7; int q,tot,minn[2][N<<2],num[2][N<<2],res1,num1,res2,num2; struct node{int op,x1,x2,yy1,y2;D k1,k2,k3;}t[N];D b[N<<2]; struct data{int y,num;}; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} il D K(int x,int y){if(x==0)return inf;return (D)y/(D)x;} il int getid(D x){return lower_bound(b+1,b+1+tot,x)-b;} il data Min(data t1,data t2){ if(t1.y<t2.y)return t1;if(t1.y>t2.y)return t2; if(t1.num<t2.num)return t2;else return t1; } void c(int op,int x,int l,int r,int ql,int qr,int y,int nn){ if(ql<=l&&r<=qr){if(minn[op][x]>=y)minn[op][x]=y,num[op][x]=nn;return;} int mid=(l+r)>>1; if(ql<=mid)c(op,x<<1,l,mid,ql,qr,y,nn); if(mid<qr)c(op,x<<1|1,mid+1,r,ql,qr,y,nn); } data query(int op,int x,int l,int r,int pos){ if(l==r)return (data){minn[op][x],num[op][x]}; int mid=(l+r)>>1;data k1,k2; if(pos<=mid)return Min((data){minn[op][x],num[op][x]},query(op,x<<1,l,mid,pos)); else return Min((data){minn[op][x],num[op][x]},query(op,x<<1|1,mid+1,r,pos)); } void build(int x,int l,int r){ minn[0][x]=minn[1][x]=inf;if(l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); } int main() { q=read();res1=res2=inf; for(int i=1;i<=q;i++){ t[i].op=read(); if(t[i].op==1){ t[i].x1=read();t[i].yy1=read(); t[i].x2=read();t[i].y2=read(); t[i].k1=K(t[i].x1,t[i].y2);b[++tot]=t[i].k1; t[i].k2=K(t[i].x1,t[i].yy1);b[++tot]=t[i].k2; t[i].k3=K(t[i].x2,t[i].yy1);b[++tot]=t[i].k3; } else{ t[i].x1=read();t[i].yy1=read();t[i].k1=K(t[i].x1,t[i].yy1); b[++tot]=t[i].k1; } } sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;build(1,1,tot); for(int i=1;i<=q;i++){ if(t[i].op==1){ c(0,1,1,tot,getid(t[i].k2),getid(t[i].k1),t[i].x1,i); c(1,1,1,tot,getid(t[i].k3),getid(t[i].k2),t[i].yy1,i); if(t[i].yy1==0&&res1>=t[i].x1)res1=t[i].x1,num1=i; if(t[i].x1==0&&res2>=t[i].yy1)res2=t[i].yy1,num2=i; } else{ data k1,k2; if(t[i].k1==0){printf("%d\n",num1);continue;} if(t[i].k1==inf){printf("%d\n",num2);continue;} k1=query(0,1,1,tot,getid(t[i].k1)); k2=query(1,1,1,tot,getid(t[i].k1)); if(k1.y*t[i].k1>k2.y){printf("%d\n",k2.num);} else if(k1.y*t[i].k1==k2.y){printf("%d\n",max(k1.num,k2.num));} else {printf("%d\n",k1.num);} } } return 0; }
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。