P3316 [SDOI2014]里面还是外面

    • 0通过
    • 2提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2014 山东 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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 1000000000Y = (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(均为小写字符),分别表示询问点在多边形的内、外或边界。

    输入输出样例

    输入样例#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

    说明

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。