AtCoder Beginner Contest(ABC) 197 D - Opposite の解説
はじめに
この間のAtCoder Beginner Contest(ABC)197のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。
D - Opposite
問題文
軸の正の向きを右、軸の正の向きを上とする次元座標平面上に、の個の頂点からなる正角形があります。 ここでは偶数であることが保証され、頂点はこの順に反時計回りに並んでいます。の座標をとします。が与えられるので、を求めてください。
制約
- は偶数
- 入力に含まれる値は全て整数である
解答までの道のり
問題文をよく見てみる
まず問題文を見て思うのは、すごく数学チックな問題だということです。 正角形の角度や辺の長さなどの性質が問題解決に役立ちそうです。
実験してみる
今回は入力例2の の場合で考えます。 この状態を図にするとこうなります。 図からは、 は、
- とを結ぶ対角線の角度から、(図では約)
- 内角の大きさのだけ角度を引いた方向に(図では約)
- から、辺の長さだけ進ませた点であることがわかります。
以上の操作をコードに落とし込ませれば良いと分かります。
必要な知識をググる
問題を解くには
- 対角線の角度
- 内角の大きさ
- 辺の長さ
が必要とわかったので、これらについての情報を集めます。
まず、対角線の角度はアークタンジェントの関数で求められます。
ただし、ここには落とし穴があり、
pythonではmath.atan
ではなく、math.atan2
を使わないと
ゼロ除算によるエラーや、極端に小さい値による除算からの誤差が出てしまいます。
これがなければ4完できたんだけどな~
また、Wikiによると、
- 正角形の内角の和はでラジアン表記では
- 辺の長さがの正角形の任意の点から番目に近い点までの距離は、である。
- つまり、とを結ぶ対角線の長さをとすると、となるため、辺の長さはとなる。
ということが分かりました。 これらのことからコードを組んでいきます。
解答
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問題のほうが難しく感じてしまう・・・。