#P3606. [Sdoi2014]里面还是外面
[Sdoi2014]里面还是外面
[SDOI2014] 里面还是外面
题目描述
Alice 给出平面上的一个简单 边形。按边界顺序连接相邻顶点,第 个顶点与第 个顶点也相邻。不同的边界线段只可能在公共端点相交。
Alice 可以询问一个点在多边形内部、外部还是边界上。多边形顶点和位于任一条边上的点均属于边界。
Alice 也可以修改多边形。删去当前连接 和 的一条边,插入新顶点 ,并连上 和 。 都是已有顶点。 与已有的顶点均不重合,也不在修改前的边界上,修改后仍是简单多边形。
每次询问给出 以及三对候选偏移。设上一次询问的点为 ,当时的答案为 ,其中 是 in、out、bd 之一。这一次要判断的点为
第一次询问以 为上一次的询问点,按它相对初始多边形的位置选取偏移。修改操作不重新计算此前的答案。输入已包含全部操作,按顺序解码并作答。
输入格式
第一行一个整数 。接下来 行,每行两个整数 ,按边界顺序给出初始多边形的顶点坐标。
接下来一行一个整数 。随后 行各描述一次操作。
- 第一个整数为 时,随后给出七个非负整数 $r,x_\mathrm{in},y_\mathrm{in},x_\mathrm{out},y_\mathrm{out},x_\mathrm{bd},y_\mathrm{bd}$,表示一次询问。
- 第一个整数为 时,随后给出六个整数 ,表示一次修改。
输出格式
对每次询问输出一行。若点在多边形内部,输出 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
数据范围
,。所有坐标均为非负整数且小于 。任意两个多边形顶点的横坐标不同,纵坐标也不同。
点 位于多边形外部。