読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

HackerRank 101 Hack 47 - Basketball Game

HackerRank

問題

問題の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}

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

あとは、求めた\tau0\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;
}

コードの説明など

上記で示した計算式をそのままコードに起こしているだけです。

なお、\mathtt{std::hypot}関数は、引数\mathtt{(x, y)}について、点(x, y)の原点からの距離を返します。
ここでは、2点(x_C, y_C), (x_h, y_h)間の距離を求めるのに使っています。


感想など

あまり幾何の問題を時間内に通したことが無かったため、通せてよかったです。

紙の上では計算式がごちゃごちゃしてしまったので、要らないところで思考の妨げにならないよう計算用紙にもコードにもキレイに式を書くように心がけたいですね。