D - Congruence Points Editorial by shakayami
以降は計算は有理数の範囲内で行うものとします。（python or pypyにはFractionというライブラリがあるため有理数計算が簡単にできます。）
まず、Sの集合の重心を計算して、重心が原点になるように平行移動をします。
Tについても同様に重心が原点となるように平行移動をします。
ここで、もしうまい具合に移動して頂点が一致できるならば、回転移動だけでOKです。理由としては、重心が原点にあるならばどのように回転移動をしても重心が原点のままになるからです。
\(S\)上の点\(s_i=(a_i,b_i)\)と\(T\)上の点\(t_j=(c_j,d_j)\)からなる\(N^2\)個の組すべてについて、点\(s_i\)を点\(t_j\)に移動させるような回転移動をした時に、集合が一致するかを判定します。
具体的には以下のようなことをします。
まず、 \(a_i^2+b_i^2=c_j^2+d_j^2\)でないならば点\(i\)を回転移動で点\(j\)に重ねることはできません。（原点を中心に回転移動するとき、原点からの距離は常に一定となります。）
\((a_i,b_i)\)と\((c_j,d_j)\)が共に原点にある場合は以降の操作が破綻するためパスをします。\(N>1\)ならば原点でないような点が\(S,T\)からそれぞれ取ることができます。 逆に、\(N=1\)ならば答えは常にYesです。
次に、\(S\)の全ての点\((x,y)\)に対して
\[(x+iy)\to (x+iy)\frac{c+di}{a+bi}\]
つまり、
\[(x,y)\to \left(\frac{acx-ady+bcy+bdx}{a^2+b^2},\frac{acy+adx-bcx+bdy}{a^2+b^2}\right)\]
という変換をします。もし変換後の集合\(S\)と集合\(T\)が一致しているならば答えはYesです。
逆に、\(N^2\)回のすべての試行に対して集合が一致しないならば答えはNoです。
集合の一致判定についてはソートして確かめればOKです。
よって各試行において、一致判定が\(O(N\log{N})\)でできるため、 全体の計算量は\(O(N^3\log{N})\)となります。\(N\leq 100\)なので十分高速です。
実装例(pypy 3)
posted:
last update: