ABC207 D Congruence PointsをPythonと複素数で解く

問題

https://atcoder.jp/contests/abc207/tasks/abc207_d

方針

入力例1の場合の図を示します。

• $S$に含まれる全ての点(図の赤の点)の重心を求める。
• $T$に含まれる全ての点(図の緑の点)の重心を求める。
• $S$の重心から$T$の重心へ向かうベクトル$\overrightarrow{v_{ST}}$を考え、$S$に含まれる全ての点にこのベクトル$\overrightarrow{v_{ST}}$を足して$S$を移動させる。
  • 移動後の$S$と$T$の重心は一致し、以降これを$G$とする。

• $S$と$T$からそれぞれ1点を選び、選んだ2点が一致するような回転角を定め、$S$に含まれる全ての点を$G$を中心として回転させる。
  • これをすべての組み合わせで試す。回転後の$S$が$T$と一致すればYesであり、すべての組で試して一致しなければNoである。
  • $N \leq 100$なので3重ループでも間に合う。

実装

import math
import cmath
import sys
from fractions import Fraction

# 標準入力
N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
T = [tuple(map(int, input().split())) for _ in range(N)]

# 重心
s_g = [Fraction(0), Fraction(0)]
t_g = [Fraction(0), Fraction(0)]

for i in range(N):
    s_g[0] += S[i][0]
    s_g[1] += S[i][1]

    t_g[0] += T[i][0]
    t_g[1] += T[i][1]

s_g[0] /= N
s_g[1] /= N

t_g[0] /= N
t_g[1] /= N

# 移動
vec_st = [t_g[0] - s_g[0], t_g[1] - s_g[1]]

for i in range(N):
    S[i][0] += vec_st[0]
    S[i][1] += vec_st[1]

# 回転中心の複素数
g_complex = complex(t_g[0], t_g[1])

# Tのin判定用
T_set = set(T)

# s, tを1組選ぶ
for s in S:
    for t in T:
        # 回転角thetaを求める
        s_complex = complex(s[0], s[1])
        t_complex = complex(t[0], t[1])

        if s_complex == g_complex:
            if s_complex == t_complex:
                theta = 0
            else:
                continue
        else:
            theta = cmath.phase((t_complex - g_complex) / (s_complex - g_complex))

        # Sを全てtheta回転する
        for i in range(N):
            s_rotated_complex = (complex(S[i][0], S[i][1]) - g_complex) * cmath.rect(1, theta) + g_complex
            s_rotated = [s_rotated_complex.real, s_rotated_complex.imag]

            # 整数に丸める
            if math.ceil(s_rotated[0]) - s_rotated[0] < 0.0001:
                s_rotated[0] = math.ceil(s_rotated[0])
            if s_rotated[0] - math.floor(s_rotated[0]) < 0.0001:
                s_rotated[0] = math.floor(s_rotated[0])
            if math.ceil(s_rotated[1]) - s_rotated[1] < 0.0001:
                s_rotated[1] = math.ceil(s_rotated[1])
            if s_rotated[1] - math.floor(s_rotated[1]) < 0.0001:
                s_rotated[1] = math.floor(s_rotated[1])

            if not tuple(s_rotated) in T_set:  # 回転後の点が元のTに含まれていなければ
                break
        else:  # forが最後まで回ったら
            print("Yes")
            sys.exit()

print("No")

標準入力

$S$は後で移動させるのでlistに、$T$は後で$O(1)$でinを使うためにsetに変換するのでtupleにします。

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
T = [tuple(map(int, input().split())) for _ in range(N)]

重心を求めて移動

重心は以下の式で求められます。

$$x_g=\frac{x_1+\cdots+x_N}{N}$$

$$y_g=\frac{y_1+\cdots+y_N}{N}$$

除算は怖いのでfractions.Fractionを使います。^[1]

https://docs.python.org/ja/3/library/fractions.html

s_g = [Fraction(0), Fraction(0)]
t_g = [Fraction(0), Fraction(0)]

for i in range(N):
    s_g[0] += S[i][0]
    s_g[1] += S[i][1]

    t_g[0] += T[i][0]
    t_g[1] += T[i][1]

s_g[0] /= N
s_g[1] /= N

t_g[0] /= N
t_g[1] /= N

vec_st = [t_g[0]-s_g[0], t_g[1]-s_g[1]]

for i in range(N):
    S[i][0] += vec_st[0]
    S[i][1] += vec_st[1]

回転して一致するか試す

ここで座標を複素数に変換します。complex型では有理数や固定少数点数が使えないようなので、変換後の点が一致する場合に座標の値が整数になることを利用して、差が十分小さい時に値を丸めることにします。

複素数平面において、複素数$s$を複素数$g$を中心として$\theta$回転したものが複素数$t$であることは以下の式で表せます。ただし虚数単位を$j$とします。^[2]

$$t-g=(s-g)e^{j \theta}=(s-g)(\cos{\theta} +j \sin{\theta})$$

よって$s\neq g$のとき、ある複素数$s$を回転させて複素数$t$に一致させる時の回転角$\theta$は以下のようになります。

$$\theta=\arg{\left(\frac{t-g}{s-g}\right)}$$

$s=g$のときは回転角を定めることができないので、$s=t=g$の場合を考慮して$\theta=0$とします。^[3]

# 回転中心の複素数
g_complex = complex(t_g[0], t_g[1])

# Tのin判定用
T_set = set(T)

# s, tを1組選ぶ
for s in S:
    for t in T:
        # 回転角thetaを求める
        s_complex = complex(s[0], s[1])
        t_complex = complex(t[0], t[1])

        if s_complex == g_complex:
            if s_complex == t_complex:
                theta = 0
            else:
                continue
        else:
            theta = cmath.phase((t_complex - g_complex) / (s_complex - g_complex))

        # Sを全てtheta回転する
        for i in range(N):
            s_rotated_complex = (complex(S[i][0], S[i][1]) - g_complex) * cmath.rect(1, theta) + g_complex
            s_rotated = [s_rotated_complex.real, s_rotated_complex.imag]

            # 整数に丸める
            if math.ceil(s_rotated[0]) - s_rotated[0] < 0.0001:
                s_rotated[0] = math.ceil(s_rotated[0])
            if s_rotated[0] - math.floor(s_rotated[0]) < 0.0001:
                s_rotated[0] = math.floor(s_rotated[0])
            if math.ceil(s_rotated[1]) - s_rotated[1] < 0.0001:
                s_rotated[1] = math.ceil(s_rotated[1])
            if s_rotated[1] - math.floor(s_rotated[1]) < 0.0001:
                s_rotated[1] = math.floor(s_rotated[1])

            if not tuple(s_rotated) in T_set:  # 回転後の点が元のTに含まれていなければ
                break
        else:  # forが最後まで回ったら
            print("Yes")
            sys.exit()

print("No")

脚注

1. この問題ではfloat型のまま計算してもACできました。

2. 数学では虚数単位として主に$i$を使いますが、工学など$i$が虚数単位以外の意味として使われる分野においては文字の重複を避けるために虚数単位として主に$j$を使うことがあります。Pythonでは虚数単位として1jを使うので式もこちらに合わせました。

3. $N=1$, $(a_1,b_1)=(c_1,d_1)=(0,0)$の入力で困るため。