【bzoj3165】【HEOI2013】【Segment】【线段树】

要求在平面直角坐标系下维护两个操作： 
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。  

 
第一行一个整数n，表示共n 个操作。 
接下来n行，每行第一个数为0或1。 
 
若该数为 0，则后面跟着一个正整数 k，表示询问与直线  
x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。 
若该数为 1，则后面跟着四个正整数 x0, y0, x 1, y 1，表示插入一条两个端点为 
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。 
其中lastans为上一次询问的答案。初始时lastans=0。 
 
 

对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。 

对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤  k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

题解： 用线段树维护每段位置分别被哪条线段覆盖。

           插入线段的时候如果这条线段对这个区间有贡献，就把它保留在这个区间。

           对于每次查询,从根一直查到底,对中途遇到的线段取最优值即可。

           注意处理斜率不存在的线段。

代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define N 100010
#define P 39989
#define MOD 1000000000
#define eps 1e-10
using namespace std;
int t[N<<2],ansa,n,y,x2,y2,kind,top,a[N],x,lastans;
double b[N],ansb;
struct use{double k,b;int l,r;double f(int x){return k*x+b;}
}line[N];
int cross(use a,use b){return floor((b.b-a.b)/(a.k-b.k));
}
use cal(int x,int y,int x2,int y2){ use ans;ans.r=max(x,x2);ans.l=min(x,x2);if (x2!=x) ans.k=(y2-y)/(double)(x2-x),ans.b=y-ans.k*x;else ans.k=0.0,ans.b=max(y,y2);return ans;
}
int check(double x){return (x>-eps)-(x<eps); 
}
void up(int k,int x){double t=line[k].f(x);int ff=check(t-b[x]);if (!a[x]||(ff>0||(ff==0&&k<a[x]))){a[x]=k;b[x]=t;} 	
}
void insert(int k,int l,int r,int x){if (line[x].l<=l&&r<=line[x].r){if (!t[k]){t[k]=x;return;}else{int fl=check(line[x].f(l)-line[t[k]].f(l))>0;int fr=check(line[x].f(r)-line[t[k]].f(r))>0; if (fl&&fr) t[k]=x;else if(fl||fr){int mid=(l+r)>>1;int p=cross(line[x],line[t[k]]);if (p<=mid&&fl) insert(k<<1,l,mid,x);if (p<=mid&&fr) insert(k<<1,l,mid,t[k]),t[k]=x;if (p>mid&&fl) insert(k<<1|1,mid+1,r,t[k]),t[k]=x;if (p>mid&&fr) insert(k<<1|1,mid+1,r,x); }else up(x,l),up(x,r);}return;}int mid=(l+r)>>1;if (line[x].l<=mid) insert(k<<1,l,mid,x);if (line[x].r>mid) insert(k<<1|1,mid+1,r,x);
}
void query(int k,int l,int r,int x){if (t[k]){double tt=line[t[k]].f(x);int ff=check(tt-ansb);if ((ff>0||(ff==0&&ansa<t[k]))){ansa=t[k];ansb=tt;}}if (l==r) return;int mid=(l+r)>>1;if (x<=mid) query(k<<1,l,mid,x);else query(k<<1|1,mid+1,r,x); 
}
int main(){scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&kind);if (kind){scanf("%d%d%d%d",&x,&y,&x2,&y2);x=(x+lastans-1)%P+1;x2=(x2+lastans-1)%P+1;y=(y+lastans-1)%MOD+1;y2=(y2+lastans-1)%MOD+1;line[++top]=cal(x,y,x2,y2);//cout<<line[top].k<<' '<<line[top].b<<' '<<line[top].l<<' '<<line[top].r<<endl;insert(1,1,P,top);}else{scanf("%d",&x);ansa=0;ansb=-1.0;x=(x+lastans-1)%P+1;query(1,1,P,x);int ff=check(b[x]-ansb);if ((ff>0||(ff==0&&a[x]<ansa))){ansa=a[x];}lastans=ansa;printf("%d\n",lastans);} }
}