2012-12-06
■ Codeforces 250D
要約：西の直線の道を渡って、川を渡って、東の曲がりくねった道を渡ったときの最短路は、どのような道の組み合わせ？
と言う問題。東の道路m本それぞれについて最短路を考える。ここで、西の道路は起点が(0,0)なので、川を渡る距離＋西の道路を渡る距離は、(0,0)と川の西岸と川の東岸が一直線上のあるとき最短。そして、一直線にできるだけ近い位置関係にあるときが望ましい。よって、現時点での東岸のy座標をa/b倍した数を西岸のeach pointのy座標をsortしてにぶたん。そして、最も近い点を経由するのが最短なので、その距離がそれまでの最短距離を下回れば更新。オーダーはO(mlogn)でしょうか。
