这道题挺有意思的。

通过两个样例的解释,发现一个规律,都是从一个机关坐标到另外一个机关坐标。

事实上,这也是最优的(臆想一下易得)。

那么现在的问题就是,当前点$i$,如何找到它的决策点$j$($i$从哪里来)。

如果一条射线方向朝上(朝上的定义等下讲),那么人就不能往上走,因为被挡住了。

方向朝下,一样的道理。

朝上朝下的定义:对于每一个点$i$,以它为极点构造极坐标系,由$i$射向$S$的直线$l_1$的极角$l$,由$i$射向$T$的直线$l_2$的极角$r$,若射线$i$的极角$t$在$l$顺时针到$r$的极角范围内,称射线$i$方向向上,反之方向朝下。

这里有一张向上的图

捕获.PNG

这个很好理解的,因为不能穿过图中射线$h$到达$T$,不能向上走,再怎么向上走,也走不到$T$。

因此对于每一个射线的方向进行编号,可以分成两类射线:向上或向下。

画个图出来:

捕获1.PNG

就是这样的(只画了一半),从左到右给它们编个号,$i,j,k,z$。

$i$直接到$k$的路径不合法,所以通过$j$到$k$。

$j$直接到$z$的路径合法,且比经过$k$的路径短,因此可以在插入$z$时,弹出$k$

那么现在问题变成了当前点$i$,找到最远且合法的决策点。

对于同一种方向的决策点,可以用上述讲的方法进行操作,并用单调队列进行优化。

但是如果出现了这种情况呢?

![](C:UsersAdministratorDesktop新建文件夹 (2)捕获2.PNG)

同样地,对它们进行编号,$i,j,k$

对于正在插入的$k$,$i$显然不是最优决策,踢掉。

那么对于之后的$z$,$i$是否能成为最优决策呢?

显然不能,$i$与$z$的连线,要么被$j$阻隔,要么被$k$阻隔,因此对于之后的状态,$i$也不可能成为决策点。

貌似就这两种情况。

upd:

其实整个图可以类比成凸壳,向上的线段在大体上看是一个上凸壳,向下的线段在大体上看是一个下凸壳。

如果插入的射线$l$与另一方向的队头的连线被阻断,那么与其同一方向的射线,要么被阻隔,要么因为不是最优决策(距离过长)而被淘汰,在另一方向上总有一条射线会更优。

因此最优决策只会产生在另一方向的射线集合中,因此可以选择清空同一方向的队列,再将最优决策插入到这一队列中。

总结一下:

  1. 对射线方向进行判断。
  2. 弄出所有有用直线出来(在$S,T$之间)
  3. 判断当前直线有没有类似第二种情况出现
  4. 若没有,直接用单调队列踢队尾
  5. 若有,对另一个单调队列踢队首。

代码就不贴了。