lb2003的个人博客

这道题挺有意思的。

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

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

那么现在的问题就是，当前点$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$与另一方向的队头的连线被阻断，那么与其同一方向的射线，要么被阻隔，要么因为不是最优决策(距离过长)而被淘汰，在另一方向上总有一条射线会更优。

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

总结一下:

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

代码就不贴了。