ABC207:D - Congruence Points #几何# #数学#
题目
https://atcoder.jp/contests/abc207/tasks/abc207_d
大意:给定两个二维平面,各有\(n\)个点,问,第一个平面上的点经过若干次整体平移或整体旋转(任意角度),能否和第二个平面的点重合
横纵坐标范围:\([-10,10]\),\(n\)范围:\([1,100]\),均为整数
思路
前置知识
已知坐标求角度
坐标为\((x,y)\)调用atan2(y,x)可求得 (该点与原点连线) 与\(x\)轴所成角
绕原点旋转坐标变化
高一以下学历慎入
设\(A\)坐标为\((x,y)\),\((r\cdot \cos \alpha , \ r\cdot \sin \alpha)\),则\(\cos \alpha=\frac{x}{r},\sin \alpha = \frac{y}{r}\),设\(A\)逆时针旋转\(\beta\)得到\(B\),则\(B(r\cdot \cos (\alpha-\beta) , \ r\cdot \sin (\alpha-\beta)\ )\)
\[\begin{align}
r\cdot \cos(\alpha -\beta) &=r\cdot (\cos\alpha\cdot \cos \beta+\sin \alpha \cdot \cos \beta) \&=r\cdot (\frac{x}{r} \cdot \cos \beta+\frac yr \cdot \sin \beta) \&=x \cdot \cos \beta+y \cdot \sin \beta\\end{align}
\]
同理,
\[\begin{align}
r\cdot \sin(\alpha -\beta) &=r\cdot (\sin\alpha\cdot \cos \beta-\cos \alpha \cdot \sin \beta) \&=r\cdot (\frac yr \cdot \cos \beta-\frac xr \cdot \sin \beta) \&=y \cdot \cos \beta-x \cdot \sin \beta\\end{align}
\]
所以,用\(x,y\)表示\(B\)为\((x \cdot \cos \beta+y \cdot \sin \beta\ ,\ y \cdot \cos \beta-x \cdot \sin \beta)\)
二维平面点的重心
定义\(n\)个点,坐标依次\((x_i,y_i)\),它们的重心为
\[(\frac{ \sum^n_{i=1}x_i} {n} , \frac{ \sum^n_{i=1}y_i} {n})
\]
若每个点坐标变为\((x_i+a,y_i+b)\),则重心坐标变为:
\[(\frac{ \sum^n_{i=1}x_i} {n}+a , \frac{ \sum^n_{i=1}y_i} {n}+b)
\]
正式思路
我们可以通过平移,将两个平面的点的重心都放到原点上.这样,我们就不用考虑原题平移的问题了.
所以,我们只需判断是否旋转重合,复杂度要求不高,直接枚举对应点即可
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 110
#define eps 1e-6
#define sqr(_) ((_) * (_))
bool equ(double _ , double __) {return fabs((_) - (__)) < eps;}
int n;
double a[N] , b[N] , c[N] , d[N];
void input(double *x , double *y) {
double gx , gy;
gx = gy = 0;
for(int i = 1 ; i <= n ; i++) {
cin >> x[i] >> y[i];
gx += x[i] , gy += y[i];
}
gx /= (double)n , gy /= (double)n;
for(int i = 1 ; i <= n ; i++) {
x[i] -= gx , y[i] -= gy;//平移
}
}
int main() {
cin >> n;
input(a , b);
input(c , d);
for(int i = 1 ; i <= n ; i++)//必须保证(a[1],b[1])不在原点(否则角度为0,无意义)
if(a[i] != 0 || b[i] != 0) {
swap(a[1] , a[i]);
swap(b[1] , b[i]);
break;
}
for(int i = 1 ; i <= n ; i++) {
if(equ(sqr(a[1]) + sqr(b[1]) , sqr(c[i]) + sqr(d[i])) == false) continue;//若A能绕原点旋转B,它们到原点的距离一定相等
double angle = atan2(b[1] , a[1]) - atan2(d[i] , c[i]);//旋转角
int cnt = 0;
for(int j = 1 ; j <= n ; j++) {
double x , y;
x = a[j] * cos(angle) + b[j] * sin(angle);//旋转变换
y = b[j] * cos(angle) - a[j] * sin(angle);
for(int k = 1 ; k <= n ; k++) {
if(equ(x , c[k]) && equ(y , d[k]))
++cnt;//没有重合点,直接这样就可以了
}
}
if(cnt == n) {
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}