Official
D - Congruence Points Editorial by penguinman
この問題には様々な解法がありますが、そのうちの \(1\) つを紹介します。
点集合 \(X=\{(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)\}\) を \(x\) 軸方向に \(q\), \(y\) 軸方向に \(r\) 移動させたとき、\(X\) の重心、すなわち \((\frac{\sum_{i=1}^{k}x_i}{k},\frac{\sum_{i=1}^{k}y_i}{k})\) も \(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)\) が重心と一致する場合の処理には気をつけましょう。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<double> a(N),b(N),c(N),d(N);
for(int _=0; _<2; _++){
for(int i=0; i<N; i++) cin >> a[i] >> b[i];
int x = 0, y = 0;
for(int i=0; i<N; i++){
x += a[i];
y += b[i];
a[i] *= N;
b[i] *= N;
}
for(int i=0; i<N; i++){
a[i] -= x;
b[i] -= y;
}
swap(a,c);
swap(b,d);
}
for(int i=0; i<N; i++){
if(a[i]!=0 || b[i]!=0){
swap(a[i],a[0]);
swap(b[i],b[0]);
}
}
string ans = "No";
const double eps = 1e-6;
for(int i=0; i<N; i++){
double angle = atan2(d[i],c[i])-atan2(b[0],a[0]);
bool flag = true;
for(int j=0; j<N; j++){
double A = a[j]*cos(angle)-b[j]*sin(angle);
double B = a[j]*sin(angle)+b[j]*cos(angle);
bool flag2 = false;
for(int k=0; k<N; k++){
if(std::abs(A-c[k])<=eps && std::abs(B-d[k])<=eps) flag2 = true;
}
flag &= flag2;
}
if(flag) ans = "Yes";
}
cout << ans << endl;
}
posted:
last update: