Official

I - 対称変換/Symmetric Transformation Editorial by leaf1415


入力で与えられた点集合 \(S\) と点集合 \(T\) がはじめから一致している場合、答えは明らかに Yes です。入力で与えられた \(S\)\(T\) が一致していない場合を以下で考えます。

このとき、\(x\) 軸に平行な直線に関する対称移動か \(y\) 軸に平行な直線に関する対称移動のどちらかによって \(S\)\(T\) を一致させられるかを判定しなければなりません。 以下で、「\(x\) 軸に平行な直線に関する対称移動によって \(S\)\(T\) を一致させられるか」を判定する方法を述べます。 \(y\) 軸に平行な直線に関する対称移動についても、同様の方法で判定可能です。

・ 「\(x\) 軸に平行な直線に関する対称移動によって \(S\)\(T\) を一致させられるか」を判定する方法

操作の際に選ぶ「 \(x\) 軸に平行な直線」の候補は無数にあるため、そのすべてを実際に試すことはできません。しかし、以下の考察によって選ぶ直線の候補を \(1\) つに絞ることができます。

まず、\(S\) の適当な \(1\) 点を選び、その \(y\) 座標を \(\bar{y}\) とします。 さらに、\(S\) の点のうち \(y\) 座標が \(\bar{y}\) であるものをすべて並べた列を \((x_{i_1}, \bar{y}), (x_{i_2}, \bar{y}), \ldots, (x_{i_k}, \bar{y})\) とします。 同様に、\(T\) の点のうち \(y\) 座標が \(\bar{y}\) であるものをすべて並べた列を \((X_{i_1}, \bar{y}), (X_{i_2}, \bar{y}), \ldots, (X_{i_{K}}, \bar{y})\) とします。 ここで \(x_{i_1} \lt x_{i_2} \lt \cdots \lt x_{i_k}\) および \(X_{i_1} \lt X_{i_2} \lt \cdots \lt X_{i_{K}}\) と仮定しても一般性を失いません。

\(x\) 軸に平行なある直線に関して対称移動を行い、その結果、 \(j = 1, 2, \ldots, k\) について点 \((x_{i_j}, \bar{y})\) が点 \((x'_{i_j}, \bar{y})\) に移ったとします。(操作によって点の \(y\) 座標は変わらないことに注意してください。) このとき、\(x'_{i_k} \lt x'_{i_{k-1}} \lt \cdots \lt x'_{i_1}\) であるので、操作によって \(S\)\(T\) が一致するには、少なくとも、点 \((x_{i_1}, \bar{y})\) は操作によって点 \((X_{i_{K}}, \bar{y})\) に移る必要があります。 したがって、\(S\)\(T\) が一致する可能性があるのは、操作の対象軸として直線 \(x = (x_{i_1} + X_{i_K}) / 2\) を選ぶときのみです。

よって、この \(1\) 本の直線のみについて実際に操作を行い、その結果、操作後の \(S\)\(T\) が一致するかを調べればよいです。

・実装におけるポイント等

\(2\) つの点集合が一致するかを判定するには、例えば、それぞれの点集合に含まれる点をある規則にしたがってソート(例えば、まず \(x\) 座標の大小でソートし、\(x\) 座標が等しいもの同士はさらに \(y\) 座標の大小でソートする)し、ソートされた列が等しいかを判定すれば良いです。

また、\((x_{i_1} + X_{i_K}) / 2\) は整数ではない場合がありますが、与えられた入力に対してあらかじめ \(S\)\(T\) のすべての点の座標の値を \(2\) 倍しておくことで、整数の範囲で取り扱うことができます。

posted:
last update: