BZOJ 3165: [Heoi2013]Segment
Description
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
Input
第一行一个整数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)%109+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%109+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。
Output
对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编
号。若不存在与直线相交的线段，答案为0。
Sample Input
6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5
Sample Output
2
0 3
HINT
对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。
题解
这道题目竟然是用线段树，我一开始就被它计算几何的假象吓住了！
我们可以把X轴想象成一颗线段树，然后用输入的线段来覆盖它。
如果新加入的线段在原来树上线段的上方，那毫无疑问就可以覆盖。
如果新加入的线段与原来树上线段有交点，那么我们计算出交点在哪边，更新交点那边的子树的线段。原树上线段取在上方更长的那个！
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include<cstdio> using namespace std; const int Maxn=100005; struct Line{ int index; int x1,y1,x2,y2; double k,b; inline void swap(int &a,int &b){int tmp=a;a=b;b=tmp;} inline int remax(int a,int b){return a>b?a:b;} Line(){index=0;k=0;b=0;} Line(int i,int a0,int b0,int c0,int d0){ index=i;x1=a0;y1=b0;x2=c0;y2=d0; if (x1>x2){swap(x1,x2);swap(y1,y2);} if (x1!=x2){ k=(double)(y2-y1)/(double)(x2-x1); b=(double)y1-(double)((double)x1*(double)k); }else{ k=0; b=remax(y1,y2); } //printf("Get B= %lf \n",b); } inline double getY(int x){ return (double)x*(double)k+(double)b; } }; Line l[Maxn]; int nume; int lastAns=0; int n,k; int x1,x2,y1,y2; const int Maxx=39999; struct Btree{ int m; int left,right; Btree(){m=0;} }; Btree tree[Maxx*4]; void build(int x,int left,int right){ tree[x].left=left; tree[x].right=right; if (left==right){ }else{ int mid=(left+right)/2; build(x*2,left,mid); build(x*2+1,mid+1,right); } } inline void swap(int &a,int &b){ int tmp=a;a=b;b=tmp; } void insert(int x,int m); inline void update(int x,int m){ if (tree[x].m==0){ tree[x].m=m; }else{ if (l[tree[x].m].getY(tree[x].left)<=l[m].getY(tree[x].left) ||(l[tree[x].m].getY(tree[x].left)==l[m].getY(tree[x].left) && m<tree[x].m)){ swap(m,tree[x].m); } if (tree[x].left==tree[x].right || l[tree[x].m].k==l[m].k) return; double x0=(double)(l[tree[x].m].b-l[m].b)/(double)(l[m].k-l[tree[x].m].k); if (x0<tree[x].left || tree[x].right<x0) return; int mid=(tree[x].left+tree[x].right)/2; if (x0<=mid) {insert(x*2,tree[x].m);tree[x].m=m;} if (x0>mid) insert(x*2+1,m); } } void insert(int x,int m){ if (l[m].x1<=tree[x].left && tree[x].right<=l[m].x2){ update(x,m); }else{ int mid=(tree[x].left+tree[x].right)/2; if (l[m].x1<=mid) insert(x*2,m); if (l[m].x2>mid) insert(x*2+1,m); } } int query(int x,int pos){ if (tree[x].left==tree[x].right){ return tree[x].m; }else{ int mid=(tree[x].left+tree[x].right)/2; int tmp; if (pos<=mid) tmp=query(x*2,pos); if (pos>mid) tmp=query(x*2+1,pos); if (l[tree[x].m].getY(pos)<l[tmp].getY(pos) ||(l[tree[x].m].getY(pos)==l[tmp].getY(pos) && tmp<tree[x].m)){ return tmp; }else{ return tree[x].m; } } } int main(){ //freopen("segment.in","r",stdin); //freopen("segment.out","w",stdout); scanf("%d",&n); build(1,1,Maxx); nume=0; for (int i=1;i<=n;i++){ scanf("%d",&k); if (k==0){ scanf("%d",&k);k=((k+lastAns-1)%39989+1); lastAns=query(1,k); printf("%d\n",lastAns); }else{ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1=(x1+lastAns-1)%39989+1; y1=(y1+lastAns-1)%int(1e9)+1; x2=(x2+lastAns-1)%39989+1; y2=(y2+lastAns-1)%int(1e9)+1; l[++nume]=Line(nume,x1,y1,x2,y2); //printf("Add Line k= %lf b= %lf \n",l[nume].k,l[nume].b); insert(1,nume); } } return 0; } |
数据>.<好孩子看不见
链接：http://pan.baidu.com/s/1c0GVnyS 密码：jdta
原文链接：BZOJ 3165: [Heoi2013]Segment
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!