SRM323 D1M Survived - ry0u

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

秒速$V$で動けて，$x$軸正の方向に秒速$U$で流される．$(x, y)$にまでに何秒でいけるか？行けない場合は$-1$を返す．

$t$秒でいけると仮定すると，以下が成り立つはずである．

$$ \begin{eqnarray} Vt {\rm cos} \theta + Ut &=& x\\ Vt {\rm sin} \theta &=& y \end{eqnarray} $$

三角関数を消したいので両辺を自乗して足す

$$ \begin{eqnarray} y ^2 &=& V ^2t ^2 {\rm sin} ^2 \theta\\ x ^2 &=& (Vt {\rm cos} \theta + Ut) ^2\\ &=& V ^2 t ^2 {\rm cos} ^2 \theta + 2VU {\rm cos} \theta t ^2 + U ^2 t ^2\\ x ^2 + y ^2 &=& V ^2t ^2 {\rm sin} ^2 + V ^2 t ^2 {\rm cos} ^2 \theta + 2VU {\rm cos} \theta t ^2 + U ^2 t ^2\\ &=& V ^2({\rm cos} ^2 \theta + {\rm sin} ^2 \theta) t ^2 + U ^2 t ^2 + 2VU{\rm cos} \theta t ^2\\ &=& (V ^2 + U ^2)t ^2 + 2Ut \times V t{\rm cos} \theta \end{eqnarray} $$

ここで，$Vt {\rm cos} \theta$は最初の式を移項して$x - Ut$であることが分かるのでこれを代入すると

$$ \begin{eqnarray} x ^2 + y ^2 &=& (V ^2 + U ^2)t ^2 + 2Ut \times (x - Ut)\\ &=& (V ^2 + U ^2)t ^2 + 2Uxt - 2U ^2t ^2)\\ &=& (V ^2 - U ^2)t ^2 + 2Uxt\\ (U ^2 - V ^2) t ^2 - 2Uxt + (x ^2 + y ^2) &=& 0 \end{eqnarray} $$

$t$についての二次方程式になったので，それぞれ係数を$a, b, c$とおいて解く．$a = 0$の場合，$bx + c = 0$となるので$x = -\frac{b}{c}$である．さらに$b = 0$である場合は定数項だけが残るで，$c = 0$の場合のみいけて(これは原点にいるということ)，それ以外は到達不可能．そうでない場合は$t$の解を解の公式使って求めた．

途中で代入をしたけど，最初から移項して自乗すれば式が簡単なことに書いていて気付いた．

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class Survived {
  public:
  double minTime(int x, int y, int V, int U) {
      double a = U * U - V * V;
      double b = -2 * U * x;
      double c = x * x + y * y;

      if(equals(a, 0.0)) {
          if(equals(b, 0)) {
              if(c == 0) return 0;
              else return -1;
          } else {
              double ans = -c / b;
              if(ans >= -EPS) return ans;
              else return -1;
          }
      }

      double d = b * b - 4 * a * c;
      if(d < -EPS) return -1;

      double t1 = (-b + sqrt(d)) / (2 * a);
      double t2 = (-b - sqrt(d)) / (2 * a);

      if(t2 > -EPS) return t2;
      if(t1 > -EPS) return t1;

      return -1;
  }
};