[Python] 幾何 ABC207D

#ABC207D

次のような認識に基づく解法が考えられる。

➀ 座標空間における回転
➁ 複素数平面における回転
➂ 辺の長さによる合同

ここでは➀に基づく解法を取る。点集合 $(X={(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)})$ を $x$ 軸方向に $q, y$ 軸方向に $r$ 移動させたとき、$X$ の重心、すなわち $(gx,gy)$ も $x$ 軸方向に $q, y$ 軸方向に $r$ 移動します。

よって $S, T$ に含まれる各点についてそれぞれ $S$ の重心、$T$ の重心からの相対的な位置関係を求めることで平行移動の影響を無視することができ、故にこれらの位置関係が回転移動のみによって一致するかを判定すればよいです。

判定の際は $(a_1,b_1)$ と対応させる点 $(c_i,d_i)$ を $i=1,2,\ldots,N$ について全探索すればよく、計算量は $O(N^2\log N)$ や $O(N^3)$ となります。$(a_1,b_1)$ が重心と一致する場合の処理には気をつけましょう。

実は、この問題を $O(N \log N)$ 、ソート部分を除いて $O(N)$ で解くこともできます。 ${\bf u_i}=(X_i-gx,Y_i-gy)$ を偏角ソートします。ただし、長さが 0 となったベクトル(高々 1 つ)は削除するものとします。こうしてソートされたものを ${\bf v}$ とします。このとき、同じ偏角をとるベクトルが複数ある場合はその長さの昇順にソートします。

サンプルコード

eps=1e-6 # 10^-6
from math import *
n=int(input())
def f():
  X,Y=[],[]
  for _ in range(n):
    a,b=map(int,input().split())
    X+=[a*n]
    Y+=[b*n]
  gx,gy=sum(X)//n,sum(Y)//n # 重心
  S=[]
  for x,y in zip(X,Y):
    dx,dy=x-gx,y-gy
    S+=[(dx,dy,atan2(dy,dx))] # atan2:arctan(y/x)
  return sorted(S)
S=f()
T=f()
for i in range(n):
  sx0,sy0,st0=S[0]
  txi,tyi,tti=T[i]
  t=tti-st0
  for j in range(n):
    sxj,syj,stj=S[j]
    txj=sxj*cos(t)-syj*sin(t)
    tyj=sxj*sin(t)+syj*cos(t)
    ng=1
    for k in range(n):
      txk,tyk,ttk=T[k]
      if abs(txj-txk)<eps and abs(tyj-tyk)<eps: ng=0
    if ng: break
  else: exit(print('Yes'))
print('No')