这道题挺有意思的。
通过两个样例的解释,发现一个规律,都是从一个机关坐标到另外一个机关坐标。
事实上,这也是最优的(臆想一下易得)。
那么现在的问题就是,当前点$i$,如何找到它的决策点$j$($i$从哪里来)。
如果一条射线方向朝上(朝上的定义等下讲),那么人就不能往上走,因为被挡住了。
方向朝下,一样的道理。
朝上朝下的定义:对于每一个点$i$,以它为极点构造极坐标系,由$i$射向$S$的直线$l_1$的极角$l$,由$i$射向$T$的直线$l_2$的极角$r$,若射线$i$的极角$t$在$l$顺时针到$r$的极角范围内,称射线$i$方向向上,反之方向朝下。
这里有一张向上的图
这个很好理解的,因为不能穿过图中射线$h$到达$T$,不能向上走,再怎么向上走,也走不到$T$。
因此对于每一个射线的方向进行编号,可以分成两类射线:向上或向下。
画个图出来:
就是这样的(只画了一半),从左到右给它们编个号,$i,j,k,z$。
$i$直接到$k$的路径不合法,所以通过$j$到$k$。
$j$直接到$z$的路径合法,且比经过$k$的路径短,因此可以在插入$z$时,弹出$k$
那么现在问题变成了当前点$i$,找到最远且合法的决策点。
对于同一种方向的决策点,可以用上述讲的方法进行操作,并用单调队列进行优化。
但是如果出现了这种情况呢?
同样地,对它们进行编号,$i,j,k$
对于正在插入的$k$,$i$显然不是最优决策,踢掉。
那么对于之后的$z$,$i$是否能成为最优决策呢?
显然不能,$i$与$z$的连线,要么被$j$阻隔,要么被$k$阻隔,因此对于之后的状态,$i$也不可能成为决策点。
貌似就这两种情况。
upd:
其实整个图可以类比成凸壳,向上的线段在大体上看是一个上凸壳,向下的线段在大体上看是一个下凸壳。
如果插入的射线$l$与另一方向的队头的连线被阻断,那么与其同一方向的射线,要么被阻隔,要么因为不是最优决策(距离过长)而被淘汰,在另一方向上总有一条射线会更优。
因此最优决策只会产生在另一方向的射线集合中,因此可以选择清空同一方向的队列,再将最优决策插入到这一队列中。
总结一下:
- 对射线方向进行判断。
- 弄出所有有用直线出来(在$S,T$之间)
- 判断当前直线有没有类似第二种情况出现
- 若没有,直接用单调队列踢队尾
- 若有,对另一个单调队列踢队首。
代码就不贴了。
0 条评论