Codeforces Beta Round #60 C - Harry Potter and the Golden Snitch
方針
vp > vs より、ある時間 t0 で補足可能なら、任意の t >= t0 で補足可能。したがって、二分探索ができる。
実装
実数を扱う問題を解いたのは始めてだったが、非常に難儀した。その分、学ぶところがたいへん多かった。
1. 浮動小数点数の精度の問題。比較はEPSを使って行う
2. 浮動小数点数の出力
#include <iomanip> cout << setprecision(12); // どのくらいいるのか知らない。適当
のようにしておかないとダメ。
3. 二分探索の終了条件
「収束したら終了」ではなく、反復数を前もって固定しておくべきだというのは知っていた。
だが、十分な回数回せば l == r となっているはずだと思い、適当に l を出力していたが、これはダメ。
精度の関係で、l != r みたいになっているかもしれず、l は条件を満たしていないかもしれない。
r を出力すべき。
4. 二分探索の失敗条件
十分反復したあと、(l + r) / 2 が条件を満たしているかで判定していたが、これはダメ。
精度の関係で、l == (l + r) / 2 < r となっているかもしれない。
反復せずに最初に r が条件を満たしているかどうかみればよい。
5. アルゴリズム
今回、軌跡全体にわたって、一気に二分探索していた。そのため、与えられた時刻にスニッチがどの
線分に載っているかを調べる必要があり(前日の Tyndex.Brome と似た状況)、面倒な実装となった。
今回は、各線分ごとに二分探索したほうがきれい
