ABC 207 D. Congruence Points 计算几何

题目链接

题解：

这道题，看起来既要平移又要旋转，挺麻烦。可以抓住一个性质，如果这两个点集可以通过旋转匹配，那么，这两个点集中的点相对重心的位置分布是相同的。

因此，我们可以先求出这两个点集中的点相对其重心的相对坐标，这样我们就能够忽略掉平移这个操作所带来的影响。

下面就要考虑能否通过旋转使两个点集匹配。

从点集$S$中选一个$x$坐标不为0的点$p$，这样可以保证有$tan$值。由于这题范围很小，因此直接暴力枚举点集$T$中的所有点转到点$p$所需的角度$\theta$，然后，判断点集$S$的剩余点转$\theta$能否与点集$T$中的某一个点匹配即可。

时间复杂度$O(n^3)$。

实现细节见代码：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-6;
int a[110], b[110], c[110], d[110];
signed main() 
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;int sumx = 0, sumy = 0;cin >> n;sumx = sumy = 0;for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];sumx += a[i];sumy += b[i];a[i] *= n;b[i] *= n;}for (int i = 0; i < n; i++) {a[i] -= sumx;b[i] -= sumy;}sumx = sumy = 0;for (int i = 0; i < n; i++) {cin >> c[i] >> d[i];sumx += c[i];sumy += d[i];c[i] *= n;d[i] *= n;}for (int i = 0; i < n; i++) {c[i] -= sumx;d[i] -= sumy;}for (int i = 0; i < n; i++) { // 找到一个x坐标不为0的点if (a[i]) {swap(a[i], a[0]);swap(b[i], b[0]);break;}}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 newa = a[j] * cos(angle) - b[j] * sin(angle);double newb = a[j] * sin(angle) + b[j] * cos(angle);bool flag1 = false;for (int k = 0; k < n; k++) {if (fabs(newa - c[k]) <= eps && fabs(newb - d[k]) <= eps) {flag1 = true;break;}}flag &= flag1;}if (flag) {cout << "Yes" << endl;return 0;}}cout << "No" << endl;return 0;
}