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

    ID: 2813 传统题 2000ms 512MiB 尝试: 51 已通过: 8 难度: 9 上传者: 标签>难度分类省选/NOI-计算几何射线法数据结构线段树套平衡树Treap维护顺序统计量叉积离线预收集坐标排序与序列处理离散化模拟与实现技巧半开区间统一CF2700

[Sdoi2014]里面还是外面

[SDOI2014] 里面还是外面

题目描述

Alice 给出平面上的一个简单 NN 边形。按边界顺序连接相邻顶点,第 NN 个顶点与第 11 个顶点也相邻。不同的边界线段只可能在公共端点相交。

Alice 可以询问一个点在多边形内部、外部还是边界上。多边形顶点和位于任一条边上的点均属于边界。

Alice 也可以修改多边形。删去当前连接 a=(xa,ya)a=(x_a,y_a) 和 b=(xb,yb)b=(x_b,y_b) 的一条边,插入新顶点 c=(xc,yc)c=(x_c,y_c),并连上 acac 和 bcbc。a,ba,b 都是已有顶点。cc 与已有的顶点均不重合,也不在修改前的边界上,修改后仍是简单多边形。

每次询问给出 rr 以及三对候选偏移。设上一次询问的点为 (x0,y0)(x_0,y_0),当时的答案为 zz,其中 zz 是 in、out、bd 之一。这一次要判断的点为

$$X=(r x_0+x_z)\bmod 10^9,\qquad Y=(r y_0+y_z)\bmod 10^9.$$

第一次询问以 (0,0)(0,0) 为上一次的询问点,按它相对初始多边形的位置选取偏移。修改操作不重新计算此前的答案。输入已包含全部操作,按顺序解码并作答。

输入格式

第一行一个整数 NN。接下来 NN 行,每行两个整数 x,yx,y,按边界顺序给出初始多边形的顶点坐标。

接下来一行一个整数 QQ。随后 QQ 行各描述一次操作。

  • 第一个整数为 00 时,随后给出七个非负整数 $r,x_\mathrm{in},y_\mathrm{in},x_\mathrm{out},y_\mathrm{out},x_\mathrm{bd},y_\mathrm{bd}$,表示一次询问。
  • 第一个整数为 11 时,随后给出六个整数 xa,ya,xb,yb,xc,ycx_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

数据范围

N,Q≤50000N,Q\le50000,r∈{0,1}r\in\{0,1\}。所有坐标均为非负整数且小于 10910^9。任意两个多边形顶点的横坐标不同,纵坐标也不同。

点 (10100,10100)(10^{100},10^{100}) 位于多边形外部。