西安集训D1T2 光线追踪 - 计几+线段树

假装是计几的线段树题

问题描述

在二维平面上,摄像机在$(0,0)$的位置,初始时平面上没有障碍物。现在执行$Q$次操作,操作有两种(假设这是第$i$次操作,$1 \leq i \leq Q$):

  1. 给定$x_0, y_0, x_1, y_1(x_0 < x_1, y_0 < y_1>)$,创建一个每条边与坐标轴平行的长方形障碍物,包含所有满足$x_0 \leq x \leq x_1$且$y_0 \leq y_1$的点(如果这个区域的某一部分已经存在障碍,则直接覆盖掉它,具体请看样例)。这个障碍物的编号为$i$。
  2. 给定向量$(x,y)$,会有一个动点从摄像机所在的$(0,0)$位置出发,以$(x,y)$所指的方向前进,直到碰到第一个障碍物为止。

对于第2种操作,输出最先碰到的障碍物的编号。若不会碰到任何障碍物,输出0。

输入格式

第一行一个正整数$Q$,表示操作总数。

接下来的$Q$行,每行第一个正整数$opi$为操作种类(保证为$1$或$2$)。如果为$1$,则加下来的四个整数$x_0, y_0, x_1, y_1(x_0 < x_1, y_0 < y_1>)$表示障碍物的位置;如果为$2$,则接下来两个正整数$x,y$表示前进的方向。

输出格式

共$R$行($R$为第$2$种操作的总数),每行一个正整数,表示第一个碰到的障碍物编号。

样例输入

10
1 3 3 10 4
1 4 2 5 6
2 6 2
1 2 8 4 10
1 0 6 3 9
2 5 2
2 8 6
2 2 9
2 4 7
1 5 7 10 10

样例输出

1
2
2
5
0

数据规模与约定

对于所有数据,保证$x0$与$y0$不全为0,$x$和$y$不全为$0$

测试点编号 $Q\leq$ $x_0,y_0,x_1,y_1,x,y\leq$ 特殊性质
1,2 1000 $10^9$
3,4 100000 $200$
5,6 100000 $10^9$ $x_0=x_1-1$
7,8,9,10 100000 $10^9$

Solution

考虑新加入的一个矩形对答案的影响,只有与$(x_0,y_0)$相邻的两条边。所以对答案有影响的点,只有$(x_0, y_1), (x_0, y_0), (x_1, y_0)$三个点。因此将操作离线,将所有矩形的这三个点与询问的$(x,y)$一起按极角排序离散化,于是每个询问就对应离散化后序列上的一个点,而修改则对应序列上的一段区间。

边分两种,横边和竖边,我们分开考虑,开两棵线段树。

对于新加入的一个矩形,我们在横边线段树上查找横边所在区间,如果当前距离原点的距离比树上记录的大就更新,并把标记赋值为$i$,竖边同理。

对于询问,就是在横线段树和竖线段树上查询一个点的值(即光线最先碰道的横边与最先碰到的竖边),然后判断哪个更优即可。

我考场上代码中写的标记永久化线段树,因为感觉这样可能会方便一点。

代码