ABC207 D - Congruence Points - かんプリンの学習記録

計算量は良くないですがすぐ思いつくので．あと，誤差におびえずに済む．

問題概要
解説
提出プログラム
感想

問題概要

二次元平面上の頂点集合 ${S}$ と ${T}$ が与えられる ${|S|=|T|=N}$ ． ${S}$ のすべて頂点 ${(x_i,y_i)}$ に対して同様に，原点中心の回転と平行移動を行って ${T}$ と一致させられるか判定せよ．

${1\leq N\leq 100\\ |x_i|,|y_i|\leq 10}$

解説

実際に回転とか平行移動をしてしまうと，座標が小数になってしまうので判定が難しそう．

問題は ${S}$ のある点を ${T}$ のある点に対応させることができるか．つまり，点の相対的な位置のみが重要となる．

${N=1}$ のとき，もちろんYes
${N=2}$ のとき， ${S,T}$ の ${2}$ 頂点間の距離が一致するときYes，そうでないときNo

以降 ${3\leq N}$ のときについて考える．

${S_1,S_2}$ と対応する ${T}$ の点を全探索する． ${S_1}$ を ${T_i}$ ， ${S_2}$ を ${T_j}$ と対応させる( ${2}$ 頂点間の距離は一致)， ${T_k}$ と ${S_3}$ が対応するためには「 ${S_1}$ と ${S_3}$ の距離 ${=}$ ${T_i}$ と ${T_k}$ の距離」と「 ${S_2}$ と ${S_3}$ の距離 ${=}$ ${T_j}$ と ${T_k}$ の距離」が成り立つ必要がある．

f:id:kanpurin:20210626221402p:plain:w300

ただし，この条件が成り立つだけではダメで，例えば以下のような物(上図の ${T}$ を反転させたもの)との区別ができない(以下の例はNo)．

f:id:kanpurin:20210626221740p:plain:w300

区別するためには点がある方向が分かるようなもの(外積など)を調べればよい．これが ${S_3}$ と ${T_k}$ で一致していれば ${S_3}$ と ${T_k}$ は対応することになる． ${S}$ のすべての点に対してのこの値( ${S_1,S_2}$ からの距離と，上記の情報をもつ値)の集合と ${T}$ のすべての点に対してのこの値の集合が一致していればYesとなる．すべての ${T_i,T_j}$ について調べるので ${O(N^2)}$ ，値の計算に ${O(N)}$ かかる．以下の提出プログラムでは実装をサボってソートして集合の比較しているので ${O(N\log N)}$ 余計にかかってるので全体で ${O(N^3\log N)}$ ．