折线的端点只有 n 个,但是折线上的点有无限个,这种情况下要考虑哪些点是有意义的,只将这些有意义的点加入最后的拓扑图里。
可以枚举边,对于每一条边,求出上面哪些点是有意义的。对于原本折线上的一条边 BC 上的点 P 是有意义的当且仅当存在一个端点 A,使得 \frac {AP} {vb}+\frac {BP} {va} 是所有 BC 上的点中最小的;或者使得 \frac {AP} {vb}+\frac {CP} {va} 是所有 BC 上的点中最小的。如果枚举 A,B,C,符合条件的 P 的位置是能被确定的。大多数题解都是用一些怪异的公式进行推导,这里提供一个初等数学的做法。
其实这是一个著名的初中数学模型——胡不归问题。
给定 A,B,C 三点,试在直线 BC 上找一点 P,使得 AP+\frac {CP} k 最小,其中 0<k<1。
构造 \angle BCB',使得 \cos \angle BCB'=\frac 1 k,作 AD\perp B'C,则 AD 与 BC 交点 P 即为所求。
证明不难:由构造过程可得 DP=\frac {CP} k,因此 AP+\frac {CP} k=DP+AP=AD。如果取 BC 上的另一个不同于 P 的点 P',作 P'D'\perp B'C,则有 AP'+\frac {CP'} k=D'P'+AP'>AD。
在原问题中,k=\frac {vb} {va},可以根据 BC 求出 AD,进而确定交点 P,只需要判断 P 是否在线段 BC 上即可。这样就可以对于每一条边,求出该边上所有有意义的点。显然点数和边数都是 \mathcal O(n^2) 的。