#概要
AtCoder ABC D問題は、２次元平面上の$N$個の整数座標の点の集合$S=\{(a_1,b_1),\ldots ,(a_N,b_N) \}$と$T=\{(c_1,d_1),\ldots ,(c_N,d_N) \}$が与えられたとき、$S$全体に並行移動・回転操作を施すことによって$T$に一致させることができるか判定するというものでした。一見簡単そうな問題ですが、黄diffとABCのD問題にしてはかなり難しい問題だったようです。公式解説等の多くでは、浮動小数点数型や複素数型の変数を使う方法が紹介されていましたが、誤差の扱いなどが気になるので、ここでは整数型だけを使ってこの問題を解く方法を考えます。
#解法
$1\le N \le 100$と制約が小さいことから、実際に平行移動・回転操作を試してみて$S$と$T$が一致しているか判定していくという方針でいきたいと思います。$N=1$の場合には、平行移動によって$S$と$T$を必ず一致させることができるので、以下では$N\ge2$として考えます。また、$(c_1, d_1)$が原点になるように$T$全体を並行移動しておきます。$(a_i,b_i)$と$(a_j, b_j)$を$(c_1, d_1)$と$(c_2, d_2)$に一致させる変換が存在するかを$i=1,\ldots ,N$, $j=1,\ldots ,N$に対して判定します。そのような変換$R$が存在する場合に、$R$によって$S$を$T$に一致させることができれば答えは"Yes"、全ての$i$, $j$に対して不可能な場合は"No"となります。ここまでは、公式解説等で説明されている方法と同じですが、$T$の点は全て整数座標であるため、$R$として$S$のいずれかの点を非整数に写すような変換を考える必要はなく、整数の範囲内で問題を解くことができます。
##手順１
最初に、$i$を一つ選び、$(a_i,b_i)$が$(c_1, d_1)=(0,0)$に一致するように$S$全体を並行移動させます。
##手順２
次に、$j$を一つ選び、$(a_i,b_i)$と$(a_j, b_j)$を$(c_1, d_1)$と$(c_2, d_2)$に一致させることができるか判定します。
これは、$(a_i,b_i)$と$(a_j, b_j)$間の距離が$(c_1, d_1)$と$(c_2, d_2)$間の距離に等しいかどうかを判定することと等価です。いま、$(a_1,b_1)$と$(c_1,d_1)$は、ともに原点に位置しているので、
{a_j}^2+{b_j}^2= c_2^2 + d_2^2
が成り立てば、手順３に進みます。この式を満たす$j$が見つからない場合は手順１に戻り、全ての$i$, $j$について上の式が成り立たない場合は、答えは"No"となります。
##手順３
$(a_j, b_j)$を$(c_2, d_2)$に写す変換$R$を考えます。この変換は原点周りの回転であるため２次元の回転行列によって$R$の行列表現を得ることができます。下の図のようにベクトル$(a_j, b_j)$とx軸の間の角度を$\theta_1$、ベクトル$(c_2, d_2)$とx軸の間の角度を$\theta_2$とすると、$R$の行列表現は、
R = \left(
\begin{array}{rr}
\cos\theta_2 & -\sin\theta_2 \\
\sin\theta_2 & \cos\theta_2 \\
\end{array}
\right)
\left(
\begin{array}{rr}
\cos(-\theta_1) & -\sin(-\theta_1) \\
\sin(-\theta_1) & \cos(-\theta_1) \\
\end{array}
\right)
となります。また、以下のように$a_j$, $b_j$, $c_2$, $d_2$をつかって$R$を書き表すことができます。
R = \left(
\begin{array}{rr}
c_2/r & -d_2/r \\
d_2/r & c_2/r \\
\end{array}
\right)
\left(
\begin{array}{rr}
a_j/r & b_j/r \\
-b_j/r & a_j/r \\
\end{array}
\right)\\
= \frac{1}{r^2}
\left(
\begin{array}{rr}
a_j c_2+b_j d_2 & b_j c_2-a_j d_2 \\
a_j d_2-b_j c_2 & a_j c_2+b_j d_2\\
\end{array}
\right) \\
= \frac{1}{r^2}
\left(
\begin{array}{rr}
p & -q \\
q & p\\
\end{array}
\right)\\
ただし、p=a_j c_2+b_j d_2,\; q=a_j d_2-b_j c_2,\; r^2=a_j^2 + b_j^2 =c_2^2 + d_2^2
ここで、$p$, $q$, $r^2$が全て整数であることを強調しておきたいと思います。
手順4
変換$R$によって、$(a_k, b_k)$が$(a_k', b_k')$ ($k=1, \ldots , N$)に写されるとします。手順３において、$R$の行列表現が得られているので、次のように$(a_k', b_k')$を求めることができます。
\left(
\begin{array}{rr}
a_k' \\
b_k' \\
\end{array}
\right)
= \frac{1}{r^2}
\left(
\begin{array}{rr}
p & -q \\
q & p\\
\end{array}
\right)
\left(
\begin{array}{rr}
a_k \\
b_k \\
\end{array}
\right)
= \frac{1}{r^2}
\left(
\begin{array}{rr}
a_k p - b_k q \\
a_k q + b_k p \\
\end{array}
\right)
$(a_k', b_k')$が整数座標でない、つまり、$a_k p - b_k q$または$a_k q + b_k p$が$r^2$で割り切れない場合には、$S$を$T$に一致させることがないため手順２に戻ります。全ての$k=1, \ldots , N$に対して$(a_k', b_k')$が整数座標になる場合は、手順5に進みます。
##手順５
変換後の点の集合$S' = \{(a_1',b_1'),\ldots ,(a_N',b_N') \}$が$T$に等しければ答えは"Yes"になり、そうでなければ、手順２に戻ります。候補となる変換$R$すべてに対して、$S$と$T$を一致させることができない場合には答えは"No"です。$R$によって、異なる二つの点が同じ点に写されることはないので、手順４の段階で$(a_k', b_k')$が$T$に含まれるか逐次判定していっても良いでしょう。
#実装例
C++による実装例です。$N$についての３重ループが出てきますが、$1 \le N \le 100$であるので実行時間制限には十分間に合います。
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i< (n); i++)
#define SQ(x) (x)*(x)
using namespace std;
int main(){
int N;
cin >> N;
vector<int> a(N), b(N), c(N), d(N);
rep(i,N) cin >> a[i] >> b[i];
rep(i,N) cin >> c[i] >> d[i];
// N=1の場合は、必ず"Yes"
if (N == 1) {
cout << "Yes" << endl;
return 0;
}
// (c_0, d_0)が原点になるように平行移動
for (int i = 1; i < N; i++) {
c[i] -= c[0];
d[i] -= d[0];
}
c[0] = 0;
d[0] = 0;
// 後のためにpairのsetにまとめておく
set<pair<int, int>> T;
rep(i,N) T.insert(make_pair(c[i],d[i]));
// (c_0, d_0)と(c_1, d_1)の間の距離の２乗
int r2 = SQ(c[1]) + SQ(d[1]);
rep(i,N) {
// (a_i, b_i)が原点になるように平行移動
rep(j,N) {
if (i == j) continue;
a[j] -= a[i];
b[j] -= b[i];
}
a[i] = 0;
b[i] = 0;
rep(j,N) {
// (a_0, b_0)と(a_1, b_1)の間の距離が(c_0, d_0)と(c_1, d_1)の間の距離に一致するか判定
if (SQ(a[j]) + SQ(b[j]) != r2) continue;
int p = a[j]*c[1] + b[j]*d[1];
int q = a[j]*d[1] - b[j]*c[1];
rep(k,N) {
int aa = a[k]*p - b[k]*q;
int bb = a[k]*q + b[k]*p;
// 回転変換後に整数になるか判定
if (aa%r2 != 0 || bb%r2 != 0) break;
aa /= r2;
bb /= r2;
// 回転変換後の点がTに含まれているか判定
if (T.count(make_pair(aa,bb)) == 0) break;
// 変換後にSの全ての点がTに含まれていれば"Yes"
if (k == N-1) {
cout << "Yes" << endl;
return 0;
}
}
}
}
// SをTに移す変換が見つからなければ"No"
cout << "No" << endl;
return 0;
}
まとめ
ABC207D問題を整数型の変数だけを使って解いてみました。回転操作などで浮動小数点型変数を使う必要があるように思われますが、整数座標から整数座標への変換だけを考えればいいため、整数の範囲内で解くことができました。公式解説には、より計算量の良い解法も紹介されているので参考にしてみてください。また、整数だけを使う別の解法もあるようです。
#参考文献