【ちょっとづつAtCode】ABC207 D – Congruence Points

ちょっとづつAtCoder

引用

(引用)

問題
要素数が共にNであるような二次元平面上の点の集合S={(a1,b1),(a2,b2),…,(aN,bN)} と T={(c1,d1),(c2,d2),…,(cN,dN)}が与えられます。
Sに対して以下の操作を 0回以上任意の順に好きなだけ繰り返すことで、Sと Tを一致させられるかを判定してください。
実数 p(0<p<360) を定め、 S に含まれる全ての点を、原点を中心に時計回りに p 度回転させる。実数 q,r を定める。
S に含まれる全ての点を、x 軸方向に q, y 軸向に r 移動させる。q, r の値域に制約はなく、特に正/負/零のいずれになってもよい。
制約
1≤N≤100
−10≤ai,bi,ci,di≤10
i≠j なら (ai,bi)≠(aj,bj)
i≠j なら(ci,di)≠(cj,dj)
入力は全て整数
AtCoder Beginner Contest 207 D – Congruence Pointsより引用

入力

入力は以下の形式で標準入力から与えられる。

N
a1 b1
a2 b2
⋮
aN bN
c1 d1
c2 d2
⋮
cN dN

出力

YesもしくはNo

考えてみましたけど、ぜんぜん解らなかったから解説読んだ

まず問題文として、
『平行移動&回転で一致するのか?』という問題だとは理解できました

解答1:外積を使う

①(N >= 3として)A-Bを固定してそれと同じ長さ(ルートは出したくないので2乗のまま)を全探索O(N^2)

②一致したらA-B → C・D・E・・・をしてセット化して
SセットとTセットで判定

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy2 = [list(map(int, input().split())) for _ in range(n)]
def length(s, t):#2次元座標(リスト)>長さ**2
    return (s[0]-t[0])**2 + (s[1]-t[1])**2

def Cross_product(vector_1, vector_2):#3次元ベクトル(リスト)>外積(タプル)後で一致を判断したい
    return (vector_1[1]*vector_2[2]-vector_1[2]*vector_2[1], vector_1[2]*vector_2[0]-vector_1[0]*vector_2[2], vector_1[0]*vector_2[1]-vector_1[1]*vector_2[0])

def length_CP(a, b, c):#2次元座標(リスト)>ac長さ、bc長さ、acとbcの外積(タプル)
    return (length(a, c), length(b, c), Cross_product([c[0]-a[0], c[1]-a[1], 0], [c[0]-b[0], c[1]-b[1], 0]))


if n >= 3:#3点以上で
    for i in range(n):
        for j in range(n):
            if i == j:#非重複順列
                continue
            else:
                if length(xy[0], xy[1]) == length(xy2[i], xy2[j]):
                    xy_set = {length_CP(xy[0], xy[1], xy[k]) for k in range(n)}
                    xy2_set = {length_CP(xy2[i], xy2[j], xy2[k]) for k in range(n)}
                    if xy_set == xy2_set:
                        print('Yes')
                        exit()
                    else:
                        pass
    else:
        print('No')
elif n == 2 and length(xy[0], xy[1]) == length(xy2[0], xy2[1]):
    print('Yes')
elif n == 1:
    print('Yes')
else:
    print('No')

解説2:A←A’に並行移動して、回転に複素数平面を使う

ああ、たしかに複素数は回転しやすい・・・

あと重心を利用するっていうのもあったみたい

コメント

タイトルとURLをコピーしました