BZPRO

#3606. [Sdoi2014]里面还是外面

内存限制：512 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

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，也就是说将(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（均为小写字符），分别表示询问点在多边形的内、外或边界。

样例

样例输入


			
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

样例输出


			
out

out

in

in

out

out

out

in

数据范围与提示

 对于100%的数据：N<=50000，Q<=50000，所有坐标非负且均小于1000000000，而r或者为1或者为0。

BZPRO Powered by Remmina.
Github Repository