苦痛でしかないのだけれども、角度を扱う練習はできる。
問題概要
$N$ 頂点の単純多角形の頂点が与えられる。この多角形は水平速度 $v \ \mathrm{m \cdot s^{-1}}$ 角速度 $w \ \mathrm{rad \cdot s^{-1}}$ で放り出されるので、地面に接触する $x$ 座標を求めよ。重力加速度は $9.8 \ \mathrm{m \cdot s^{-2}}$ とする。
解法
各頂点について、その点のみを考えてみる。点が重心を中心として回転運動しているとき、その点が $y \lt 0$ を満たすのはいつかを求める。
回転を考えると、 $y \lt 0$ という条件は時間について単調性を満たさない。しかし、重心の真上に点があるタイミングから $1$ 回転する間の期間のみを考えると、 $y$ 座標は unimodal なので三分探索が使える。また、この期間をサイクルとして $1, 2, \dots $ 番目のサイクル内の $y$ 座標の最小値をそれぞれ求めると、それには単調性がある。
なので、まず $y \lt 0$ を初めて満たすようなサイクルを二分探索と三分探索で求めて、それからいつ最初に $y \lt 0$ を満たすかを二分探索で求められる。これを全ての頂点について行えば衝突時間と衝突する頂点がわかるので、計算量 $O(n \log^2 \max Y)$ で解ける。
雑記
atan2(y, x) という関数が $[-\pi, \pi]$ の範囲で引数の点の角度を返してくれるので、これを用いることになる。ただ単調性のあるサイクルが始まるのが $\theta = \displaystyle \frac{\pi}{2}$ からの $2\pi$ の区間なので、丁寧に変換をする必要がある。
コメント