【競技プログラミング】AtCoder Beginner Contest 197_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

正N角形の性質と与えられた情報を利用して、中心点を求める。
その中心を基準に回転変換を行うことでp1の座標を計算する。

解法手順

1. 入力からN, (x0, y0), (xN/2, yN/2)を取得する。

2. 正N角形の中心座標(Ox, Oy)を計算する。

   • Ox = (x0 + xN/2) / 2
   • Oy = (y0 + yN/2) / 2

3. 正N角形の1辺に対応する回転角度radを計算する。

   • rad = π / (N/2)

4. 回転変換関数rotateを定義する。

   • 中心を原点とする座標系に変換
   • 回転行列を適用
   • 元の座標系に戻す

5. p0(x0, y0)を中心(Ox, Oy)周りにrad回転させて、p1(x1, y1)を求める。

   • (x1, y1) = rotate(x0, y0, Ox, Oy, rad)

6. 求めたx1とy1を出力する。

ACコード

ac.py

import math

def solve(N, x0, y0, xN2, yN2):
    # 2. 正N角形の中心座標(Ox, Oy)を計算する
    Ox = (x0 + xN2) / 2
    Oy = (y0 + yN2) / 2

    # 3. 正N角形の1辺に対応する回転角度radを計算する
    rad = math.pi / (N / 2)

    # 5. p0(x0, y0)を中心(Ox, Oy)周りにrad回転させて、p1(x1, y1)を求める
    x1, y1 = rotate(x0, y0, Ox, Oy, rad)

    # 6. 求めたx1とy1を出力する
    print(f"{x1:.10f} {y1:.10f}")

# 4. 回転変換関数rotateを定義する
def rotate(x, y, cx, cy, angle):
    # 中心を原点とする座標系に変換
    x -= cx
    y -= cy
    
    # 回転行列を適用
    new_x = x * math.cos(angle) - y * math.sin(angle)
    new_y = x * math.sin(angle) + y * math.cos(angle)
    
    # 元の座標系に戻す
    new_x += cx
    new_y += cy
    
    return new_x, new_y

if __name__=="__main__":
    # 1. 入力からN, (x0, y0), (xN/2, yN/2)を取得する
    N = int(input())
    x0, y0 = map(float, input().split())
    xN2, yN2 = map(float, input().split())
    solve(N, x0, y0, xN2, yN2)