解いた問題のソースコードと解説など。


SRM 323 Div1 Medium Survived

問題

あなたは川の中にいて、2次元座標上の原点から目的地(x,y)に向かって速さVで泳ぎだす。川はx軸正方向に速さUで流れている。目的地に着くための最小の時間を求めよ。

やりかた

t秒後に着くとすると、ある方向に距離Vt進んでいった時にちょうどゴールにつくと考えれば下の図のようになる。

f:id:Area1:20150318021538p:plain

すると(x - Ut)^2 + y^2 = (Vt)^2が成り立つので、非負解を求めればいい。2つあれば小さい方を、非負解がない・式が不能であれば-1を返す。

以下ソース。

class Survived {
public:
  double minTime(int x, int y, int V, int U){
    int A = U * U - V * V, B = -2 * U * x, C = x * x + y * y;
    cout << A << " " << B << " " << C << endl;
    if(A < 0) A *= -1, B *= -1, C *= -1;
    if(A == 0){
      if(B == 0) return C == 0 ? 0 : -1;
      else return (B * C <= 0) ? -C * 1.0 / B : -1;
    }else{
      int D = B * B - 4 * A * C;
      if(D < 0) return -1;
      
      double t1 = (-B + sqrt(D)) * 0.5 / A;
      double t2 = (-B - sqrt(D)) * 0.5 / A;
      if(t2 >= 0.0) return t2;
      if(t1 >= 0.0) return t1;
      return -1;
    }
  }
};
しょげないでよBaby 眠れば治る