HackerRank 101 Hack 47 - Basketball Game

問題

問題のURLはこちらです。
Programming Problems and Competitions :: HackerRank

問題概要

ボールが始点 $(x_C, y_C)$ から終点 $(x_{hoop}, y_{hoop})$ （以降、 $(x_h, y_h)$ と記載します）へ速さ $s_C$ で等速直線運動します。
5人の選手はこれを妨害するために、最適な動きをします。選手 $i$ は、 $(x_i, y_i)$ から速さ $s_i$ で移動します。
ボールと選手の座標が一致すると妨害が成立します。

このとき、ボールは妨害されずに終点までたどり着くことが出来るでしょうか？

なお、任意の $i$ について $(x_C, y_C)\neq (x_i, y_i)$ が成り立ちます。

考えたこと

紙の上でゴリゴリ計算していきます。
f:id:satanic0258:20170322043138p:plain

まず、上記画像のように、時刻 $t$ でのボールの位置 $\left( p_x(t), p_y(t) \right)$ 、
および時刻 $t$ で選手 $i$ がたどり着ける領域の円の半径 $r_i(t)$ を定めます。

これらは、実際に $t$ の式で書き表すと次のようになります:
$\displaystyle \begin{eqnarray} p_x(t) &=& \cfrac{T-t}{T}x_C + \cfrac{t}{T}x_{h} \\ p_y(t) &=& \cfrac{T-t}{T}y_C + \cfrac{t}{T}y_{h} \\ r_i(t) &=& s_i t \end{eqnarray}$

ただし、 $T$ はボールが終点に到達した時刻であり、 $T=\cfrac{\sqrt{(x_{h}-x_C)^2 + (y_{h}-y_C)^2}}{s_C}$ です。

すなわち、 $t$ の動く範囲は $0\leq t \leq T$ となりますが、少し式が煩雑になってしまうため、
新たに時刻の変数 $\tau = \cfrac{t}{T}$ を導入します。

このとき、 $\tau$ の動く範囲は $0\leq \tau \leq 1$ となり、上記 $t$ の関数は
$\displaystyle \begin{eqnarray} p_x(\tau) &=& (1-\tau)x_C + \tau x_{h} \\ p_y(\tau) &=& (1-\tau)y_C + \tau y_{h} \\ r_i(\tau) &=& s_i T \tau \end{eqnarray}$

となります。少し見やすくなりました。

準備が出来たので、ボールの進行が妨害されるかどうかの判定について考えていきます。

ボールの進行が妨害されてしまうとき、それは、ある時刻で選手が移動できる領域の中にボールが入っているときとなります。

さらに言うと、始めは移動できる領域の円の半径が $0$ であり、その領域内にボールは入っていないことから、
ある時刻で移動可能領域の円周上にボールが存在したとき、ボールの進行が妨害されることが分かります。
(制約より始点と選手の始めの位置が一致することはありません)

つまり、この問題は「ある動点が円周上にあるような時刻 $t$ は存在するか？」という問題と言い換えることが出来ます。

では、以上を用いて時刻 $\tau$ を求めていきます。

選手 $i$ が時刻 $\tau$ で移動できる領域の円の方程式は、
$(x-x_i)^2+(y-y_i)^2={r_i(\tau)}^2$
となります。

よって、ボール $\left( p_x(\tau), p_y(\tau) \right)$ が円周上にあるとき、次が成り立ちます:
$\left(p_x(\tau)-x_i\right)^2+\left(p_y(\tau)-y_i\right)^2={r_i(\tau)}^2$

あとは、これを $\tau$ について解くだけです(これが少々大変ですが)。

$\displaystyle \begin{eqnarray} (p_x(\tau)-x_i)^2+(p_y(\tau)-y_i)^2 &=& {r_i(\tau)}^2 \\ \{(1-\tau)x_C + \tau x_{h}-x_i\}^2+\{(1-\tau)y_C + \tau y_{h}-y_i\}^2 &=& (s_i T \tau)^2 \\ \{ (x_{h} - x_C)\tau + (x_C - x_i) \}^2 + \{ (y_{h} - y_C)\tau + (y_C - y_i) \}^2 &=& s_i^2 T^2 \tau^2 \end{eqnarray}$

字数の都合上、 $a_x = x_{h} - x_C, b_x = x_C - x_i, a_y = y_{h} - y_C, b_y = y_C - y_i$ と置きます。

$\displaystyle \begin{eqnarray} \{ a_x\tau + b_x \}^2 + \{ a_y\tau + b_y \}^2 &=& s_i^2 T^2 \tau^2 \\ ( a_x^2\tau^2 + 2a_x b_x \tau + b_x^2 ) + ( a_y^2\tau^2 + 2a_y b_y \tau + b_y^2 ) &=& s_i^2 T^2 \tau^2 \\ (a_x^2 + a_y^2 - s_i^2T^2)\tau^2 + 2(a_x b_x + a_y b_y)\tau + (b_x^2 + b_y^2) &=& 0 \end{eqnarray}$

この式を見てみると、 $\tau$ の二次方程式になっていることが分かります。

簡単のために、 $A=a_x^2 + a_y^2 - s_i^2T^2, B=a_x b_x + a_y b_y, C=b_x^2 + b_y^2$ とおくと、
$\displaystyle A\tau^2 + 2B\tau + C = 0$
となります。

ここで、 $A=0$ かつ $B=0$ の場合は解なし、
$A=0$ の場合は一次方程式として解くことに注意します。

よって、

$A=0$ かつ $B=0$ のとき解なし、
$A=0$ のとき、

$\tau = -\cfrac{C}{2B}$

それ以外のとき、解の公式より、

$\tau = \cfrac{-B\pm \sqrt{B^2-AC}}{A}$

となることが分かります。

あとは、求めた $\tau$ が $0\leq \tau < 1$ を満たしているかを調べればよいです。
（ボールが到着した時刻 $\tau = 1$ での妨害は無効であることに注意します）

これを各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;
}