はじめに

この間のAtCoder Beginner Contest(ABC)197のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

D - Opposite

問題文

$x$ 軸の正の向きを右、 $y$ 軸の正の向きを上とする $2$ 次元座標平面上に、 $p_0, p_1, p_2, \dots, p_{N-1}$ の $N$ 個の頂点からなる正 $N$ 角形があります。ここで $N$ は偶数であることが保証され、頂点 $p_0, P_1, p_2, \dots, p_{N-1}$ はこの順に反時計回りに並んでいます。 $p_i$ の座標を $(x_i, y_i)$ とします。 $x_0, y_0, x_{\frac{N}{2}}, y_{\frac{N}{2}}$ が与えられるので、 $x_1, y_1$ を求めてください。

制約

$4 \leq N \leq 100$
$N$ は偶数
$0 \leq x_0, y_0 \leq 100$
$0 \leq x_{\frac{N}{2}}, y_{\frac{N}{2}} \leq 100$
$(x_0, y_0) \neq (x_{\frac{N}{2}}, y_{\frac{N}{2}})$
入力に含まれる値は全て整数である

解答までの道のり

問題文をよく見てみる

まず問題文を見て思うのは、すごく数学チックな問題だということです。 正 $N$ 角形の角度や辺の長さなどの性質が問題解決に役立ちそうです。

実験してみる

今回は入力例2の $N=6, (x_0, y_0)=(5, 3), (x_{\frac{N}{2}}, y_{\frac{N}{2}}) = (7, 4)$ の場合で考えます。この状態を図にするとこうなります。

f:id:fwatty:20210328111053p:plain — 入力例2における図

図からは、 $(x_1, y_1)$ は、

$(x_0, y_0)$ と $(x_{\frac{N}{2}}, y_{\frac{N}{2}})$ を結ぶ対角線の角度から、（図では約 $26.565 ^{\circ}$ ）
内角の大きさの $\frac{1}{2}$ だけ角度を引いた方向に（図では約 $26.565-60 = -33.434 ^{\circ}$ ）
$(x_0, y_0)$ から、辺の長さ $a$ だけ進ませた点であることがわかります。

以上の操作をコードに落とし込ませれば良いと分かります。

必要な知識をググる

問題を解くには

対角線の角度
内角の大きさ
辺の長さ

が必要とわかったので、これらについての情報を集めます。

まず、対角線の角度はアークタンジェントの関数で求められます。ただし、ここには落とし穴があり、 pythonではmath.atanではなく、math.atan2を使わないとゼロ除算によるエラーや、極端に小さい値による除算からの誤差が出てしまいます。 ~~これがなければ4完できたんだけどな～~~

また、Wikiによると、

正 $N$ 角形の内角の和は $\dfrac{180(N-2)}{N}$ でラジアン表記では $\dfrac{\pi (N-2)}{N}$
$1$ 辺の長さが $a$ の正 $N$ 角形の任意の点から $m$ 番目に近い点までの距離は、 $\dfrac{a \sin \frac{m\pi}{N}}{\sin \frac{\pi}{N}}$ である。
つまり、 $(x_0, y_0)$ と $(x_{\frac{N}{2}}, y_{\frac{N}{2}})$ を結ぶ対角線の長さを $L$ とすると、 $m=\dfrac{N}{2}$ となるため、辺の長さ $a$ は $a = \dfrac{L \sin \frac{\pi}{N}}{\sin \frac{\pi}{2}} = L\sin \dfrac{\pi}{N}$ となる。

ということが分かりました。これらのことからコードを組んでいきます。

解答

import math

def LI(): return list(map(int, input().split()))

N = int(input())
x0, y0 = LI()
x_half, y_half = LI()

# (x_0, y_0)と(x_half, y_half)を結ぶ対角線の長さ
L = ((x0-x_half)**2 + (y0-y_half)**2)**0.5
# 1辺の長さ
a = L*math.sin(math.pi/N)
# 対角線の角度
rad = math.atan2((y_half-y0), (x_half-x0))
# 対角線の角度 - 内角の角度/2
theta = rad-0.5*math.pi*(N-2)/N
# 座標を動かす
print(x0+a*math.cos(theta), y0+a*math.sin(theta))

まとめ

アルゴリズムというより数学って感じの問題なので、アルゴリズムを知っていなければ解けないという感じではなく個人的にはとっかかりやすかったです。今回はB問題にめちゃくちゃ時間がかかったため、時間が足りず正解できなかったのが心残りです。なんか、最近C問題よりB問題のほうが難しく感じてしまう・・・。

フワッティーの挑戦日記

深層学習、Atcoderなどの勉強の軌跡を綴っていきます

AtCoder Beginner Contest(ABC) 197 D - Opposite の解説