公式解説では、部分点(40%) を取る方法として、出発地点と折り返し地点を固定した際に最短を計算する方法を紹介しています。
この方法は、Li Chao Tree を用いることで折り返し地点のみの固定で同時に更新できます。