/ Vijos / 题库 /

里面还是外面

里面还是外面

描述

Alice 给出了平面上的一个简单N-多边形。所谓简单N-多边形,包括N 个给定的端点,和连接相邻点的直线段,特别的,我们认为1 号点与N 号是相邻的。对于边界上不同的直线段,保证它们只会在公共端点处相交。

有的时候Alice 会指着平面上一个点,然后问Bob:“这个点是在多边形的里面呢,还是外面呢,还是在边界上呢?”

这个时候,如果她所指的点是多边形的一个顶点或者在多边形某条边的边界上,都将被认为是在多边形的边界上。

还有的时候,Alice 为了加大难度,会删除连接a 和b 的边,并插入新的点c(新插入的点保证不与任何已有的端点重合,也不在任何边界上),然后新增a到c 的边与b 到c 的边,从而得到一个新的简单多边形。

Alice 保证这样的操作得到的新图形总是简单多边形。

Bob 要做的,就是准确回答出Alice 的提问。而实际上,Alice 的每一次提问都将由Bob 上一次的回答决定,虽然这个回答是唯一的,但却意味着**如果Bob不能回答出前一个问题,就不能拿到Alice 的下一个问题。不过,Alice 对多边形的修改确实事先准备好的。**

详细来说:Alice 的每一次修改命令可以看作是一个六元组:

〈x_a,y_a,x_b,y_b,x_c,y_c〉

表示删除了坐标位置(x_a,y_a),与坐标位置(x_b,y_b)的点之间的连边,并插入新的点(x_c,y_c)。这里我们保证坐标为(x_a,y_a)的点与坐标为(x_b,y_b)的点总是存在的。

因为Alice 保证了所有出现的点(这包括了询问点)的坐标都是非负整数,且都小于1000000000,且多边形中(这不包括询问点)任意两个点的x 坐标不同,y 坐标也不同。

所以每一次询问Alice 将给出7 个非负整数:

r,x_{in},y_{in},x_{out},y_{out},x_{bd},y_{bd}

而Alice 这一次询问真正要询问的点(X,Y)的坐标将由上一次询问的点(x_0,y_0)与上一次询问的回答而决定。例如,若上一次询问的点在多边形外,则:

X = (r * x_0 + x_{out}) mod 1000000000

Y = (r * y_0 + y_{out}) mod 1000000000

对于第一次讯问,我们假设x_0 = y_0 = 0。

格式

输入格式

输入文件的第一行有一个整数N,表示初始时多边形的点数。

之后N 行,每行一对非负整数x 和y(0<=x,y<1000000000)。按照某一顺序依次描述了多边形的所有顶点的坐标,并编号为1 到N。

这里我们只认为,对于平面上的一点(10^100,10^100)一定是处在多边形以外的。

之后一行有一个整数Q,表示总的操作次数。

之后Q 行,每行第一个数字p,如果p=0,则表示询问,如果p=1,则表示修改。

对于询问,之后给出了7 个非负整数,它们是:

r,x_{in},y_{in},x_{out},y_{out},x_{bd},y_{bd}

对于修改,之后给出了6 个整数,它们是:

x_a,y_a,x_b,y_b,x_c,y_c

输出格式

对于每一次询问操作,单独输出一行且只包含一个字符串,它或者是in、或者是out、或者是bd(均为小写字符),分别表示询问点在多边形的内、外或边界。

样例1

样例输入1

6
249999999 499999998
583333331 83333333
83333333 333333332
333333332 999999996
833333330 749999997
499999998 833333330
12
0 1 872826049 679758020 472526437 270998755 15447952 502239247
1 833333330 749999997 499999998 833333330 916666663 666666664
1 833333330 749999997 916666663 666666664 416666665 916666663
0 1 371653715 747730364 409617871 21996163 118531999 759280767
1 249999999 499999998 583333331 83333333 666666664 166666666
0 1 195920917 488293591 322952040 262793733 678458193 506876149
0 1 203963007 782710007 391614158 831643205 340800821 896322422
0 1 498571077 461554269 765704840 973009111 152064733 114249255
1 499999998 833333330 249999999 499999998 999999996 583333331
0 1 159294077 702544938 787871788 619972292 941209243 950700951
0 1 791254252 411705638 382076333 263993056 306662346 47793905
0 1 13359599 513224793 415037020 28305143 48117026 34994422

样例输出1

out
out
in
in
out
out
out
in

限制

对于10%的数据:N<=1000,Q<=5000。
存在10%的数据:N<=1000,Q<=50000,没有修改操作。
存在20%的数据:N<=50000,Q<=50000,没有修改操作。
存在10%的数据:N<=50000,Q<=50000,每次询问操作的系数r 都恒为0。
存在20%的数据:N<=50000,Q<=50000,每一次修改操作中,x 或者与a的横坐标相差不超过1,或者与b 的横坐标相差不超过1。
对于100% 的数据: N<=50000 , Q<=50000 , 所有坐标非负且均小于1000000000,而r 或者为1 或者为0。

来源

SDOI2014

信息

ID
1870
难度
9
分类
数据结构 | 计算几何 点击显示
标签
递交数
16
已通过
1
通过率
6%
上传者

相关

在下列训练计划中:

RP++分类题库