HackerRank 101 Hack 47 - Basketball Game
問題
問題のURLはこちらです。
Programming Problems and Competitions :: HackerRank
問題概要
ボールが始点から終点(以降、と記載します)へ速さで等速直線運動します。
5人の選手はこれを妨害するために、最適な動きをします。選手は、から速さで移動します。
ボールと選手の座標が一致すると妨害が成立します。
このとき、ボールは妨害されずに終点までたどり着くことが出来るでしょうか?
なお、任意のについてが成り立ちます。
考えたこと
紙の上でゴリゴリ計算していきます。
まず、上記画像のように、時刻でのボールの位置、
および時刻で選手がたどり着ける領域の円の半径を定めます。
これらは、実際にの式で書き表すと次のようになります:
ただし、はボールが終点に到達した時刻であり、です。
すなわち、の動く範囲はとなりますが、少し式が煩雑になってしまうため、
新たに時刻の変数を導入します。
このとき、の動く範囲はとなり、上記の関数は
となります。少し見やすくなりました。
準備が出来たので、ボールの進行が妨害されるかどうかの判定について考えていきます。
ボールの進行が妨害されてしまうとき、それは、ある時刻で選手が移動できる領域の中にボールが入っているときとなります。
さらに言うと、始めは移動できる領域の円の半径がであり、その領域内にボールは入っていないことから、
ある時刻で移動可能領域の円周上にボールが存在したとき、ボールの進行が妨害されることが分かります。
(制約より始点と選手の始めの位置が一致することはありません)
つまり、この問題は「ある動点が円周上にあるような時刻は存在するか?」という問題と言い換えることが出来ます。
では、以上を用いて時刻を求めていきます。
選手が時刻で移動できる領域の円の方程式は、
となります。
よって、ボールが円周上にあるとき、次が成り立ちます:
あとは、これをについて解くだけです(これが少々大変ですが)。
字数の都合上、と置きます。
この式を見てみると、の二次方程式になっていることが分かります。
簡単のために、とおくと、
となります。
ここで、かつの場合は解なし、
の場合は一次方程式として解くことに注意します。
よって、
- かつのとき解なし、
- のとき、
- それ以外のとき、解の公式より、
となることが分かります。
あとは、求めたがを満たしているかを調べればよいです。
(ボールが到着した時刻での妨害は無効であることに注意します)
これを各5人について同じように調べていけばよいです。
コード(C++)
https://www.hackerrank.com/contests/101hack47/challenges/basketball-game/submissions/code/1301047104
#include <iostream> #include <algorithm> #include <vector> #define REP(i, n) for(int i=0;i<int(n);++i) constexpr double EPS = 1e-9; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int Q; std::cin >> Q; while (Q--) { int xh, yh, xc, yc, sc; std::cin >> xh >> yh >> xc >> yc >> sc; std::vector<int> x(5), y(5), s(5); REP(i, 5) { std::cin >> x[i] >> y[i] >> s[i]; } double T = std::hypot(xh - xc, yh - yc) / sc; bool no = false; REP(i, 5) { double A = std::pow(xh - xc, 2) + std::pow(yh - yc, 2) - s[i] * s[i] * T * T; double B = (xh - xc) * (xc - x[i]) + (yh - yc) * (yc - y[i]); double C = std::pow(xc - x[i], 2) + std::pow(yc - y[i], 2); if (std::abs(A) < EPS) { if (std::abs(B) < EPS) { continue; } double t = -C / 2 / B; if (0 <= t && t < 1) no = true; } else { double t = (-B + std::sqrt(B * B - A * C)) / A; // + if (0 <= t && t < 1) no = true; t = (-B - std::sqrt(B * B - A * C)) / A; // - if (0 <= t && t < 1) no = true; } } if (no) { std::cout << "NO\n"; } else { std::cout << "YES\n"; } } return 0; }
コードの説明など
上記で示した計算式をそのままコードに起こしているだけです。
なお、関数は、引数について、点の原点からの距離を返します。
ここでは、2点間の距離を求めるのに使っています。
感想など
あまり幾何の問題を時間内に通したことが無かったため、通せてよかったです。
紙の上では計算式がごちゃごちゃしてしまったので、要らないところで思考の妨げにならないよう計算用紙にもコードにもキレイに式を書くように心がけたいですね。