SRM 623 Div2 Medium CatAndRat

問題

SRM 623 - TopCoder Wiki

半径Rの円のチューブがある. ねずみはこのチューブの任意の方向にVratの速度で移動する. ねずみがチューブの中に入ってT秒後,猫もネズミが入ったのと同じ場所から入って, 同じようにVcatの速度で移動する. ねずみは猫から逃げ,猫がねずみを追う時,猫がねずみを捕まえるのにかかる最小の時間を求める問題.

解答

  • まず,猫が入る前にねずみは入り口から一番遠いところにいるのが良い.
  • 猫が入った時にねずみとの距離がdとする.
  • 最適な行動をとった時,猫とねずみは同じ方向に移動する.
  • 答えはd / (Vcat - Vrat)となる.
class CatAndRat
{
public:
  const double PI  = acos(-1.0);
  double getTime(int R, int T, int Vrat, int Vcat)
    {
      if (Vrat >= Vcat) return -1.0;
      double d = min(1.0 * T * Vrat, R * PI);
      return d / (Vcat - Vrat);
    }
};