D - Opposite Editorial by QCFium
\(p_0\) と \(p_{\frac{N}{2}}\) の中点を \(q\) とすると、\(p_0, p_1, p_2, \dots, p_{N - 1}\) は全て \(q\) を中心とする \(1\) つの円上に乗っているという性質があります。
また、角 \(p_0qp_1 = \frac{360^\circ}{N} = \frac{2 \pi}{N}\) です。(\(p_0, p_1, p_2, \dots, p_{N - 1}\) が円上に均等に乗っていることを考えるとよいです)
よって、\(p_1\) の座標は以下のように求められます。
- \(q\) の座標を求める
- \(q\) から見た \(p_0\) の”方位”を求める(C++ における
atan2
関数や Python におけるmath.atan2
関数を使うと実現できる) - 求めた方位を \( \frac{2 \pi}{N}\) だけ反時計回りにずらし、\(q\) から見た \(p_1\) の”方位”を求める
- \(p_1\) の \(\mathrm{x}, \mathrm{y}\) 座標を求める (\(\sin, \cos\) 関数を使うと”方位”から \(x, y\) が求まります)
atan2
関数とは
C++ の atan2
関数もPython の math.atan2
関数も基本的に同じものです
\(x, y\) を引数にとり (ただし \(y, x\) の順にとるので注意)、ベクトル \((x, y)\) の指す”向き”を返します
向きは右向き \((\mathrm{x}\) 軸の正の向き \()\) を \(0\) とし、反時計回りを正とするラジアンで返されます
例えば \(\mathrm{atan2}(0, 3) = 0\) です。\((x = 3, y = 0\) なので右向きだから \()\)
また、 \(\mathrm{atan2}(2, 0) = \frac{\pi}{2}\) です。\((x = 0, y = 2\) は上方向、つまり右方向から \(\frac{\pi}{2}\) だけ反時計回りに回した方向だから \()\)
ただし、\(2\pi\) で \(1\) 周するので返される値は \((-\pi, \pi]\) の範囲と決まっています。この問題ではこれはあまり考えなくてもよいです \((\mathrm{x}, \mathrm{y}\) 座標を復元する際の \(\sin, \cos\) 関数も \(2\pi\) の周期を持ち、引数の範囲に制限はないので \()\)
posted:
last update: